Description

Input

第一行兩個(gè)數(shù)n，q 表示士兵數(shù)以及閱兵次數(shù)。
接下來(lái)一行n-1 個(gè)整數(shù)，第i 個(gè)整數(shù)表示士兵i+1 的直屬教官。
接下來(lái)n 行每行兩個(gè)整數(shù)i i b ,l 描述一位士兵的屬性。
接下來(lái)q 行每行一個(gè)整數(shù)i s ，表示這次閱兵的總指揮。

Output

對(duì)于每次閱兵輸出一行一個(gè)整數(shù)，表示閱兵隊(duì)伍能展現(xiàn)出的最大精神力P。

Sample Input

輸入1：

5 2
1 1 2 2
2 1
1 5
4 2
2 3
3 1
1
2

輸入2：

7 3
1 1 2 2 3 3
3 0
1 3
5 2
2 0
4 1
3 1
2 2
1
2
3

Sample Output

輸出1：

3
3

樣例1 解釋：

第一次閱兵時(shí)無(wú)法進(jìn)行指導(dǎo)
第二次閱兵時(shí)令士兵3 指導(dǎo)士兵4

輸出2：

4
3
5

Data Constraint

30%的數(shù)據(jù)：n,q≤30
另有10%的數(shù)據(jù)：所有Si 均為1
另有20%的數(shù)據(jù)：q≤50
另有20%的數(shù)據(jù)：士兵i 的直屬教官為i-1
100%的數(shù)據(jù)： 1<=n,q<=2*10^5,0<=bi,li<=10^9,bi>=1,1<=Si<=n

Solution

• 這題的話我們需要處理一個(gè)點(diǎn)的子樹(shù)內(nèi)的問(wèn)題，于是我們按照DFS序遍歷一遍。

• 我們發(fā)現(xiàn)要使 P 值更大，肯定是讓模數(shù)越大越好，同時(shí)被除數(shù)也要變大。

• 于是我們先考慮不讓別的士兵“指導(dǎo)”的情況，那肯定是直接用次大值模最大值。

• 如果“指導(dǎo)”呢？先找出與答案有關(guān)的量：

• 設(shè)子樹(shù)內(nèi)b的最大值為 mx 、次大值為 mx1 、嚴(yán)格次大值為 ymx1 、嚴(yán)格第三大值為 ymx2 。

• 再設(shè)子樹(shù)外 l 的最大值為 x ，嚴(yán)格次大值為 y 。

• 如果有 mx1+x<mx ，則答案就是 mx1+x （直接提升次大值）。

• 如果有 mx1+x>mx ，則答案就為 mx （仍然直接提升次大值并當(dāng)作模數(shù)）。

• 如果有 mx1+x=mx ，那么還要繼續(xù)討論：

• 取 mx1+y

• 取 ymx2+x

• 取 ymx1

• 將以上情況取最大值即可，上述的每個(gè)量都可以用線段樹(shù)維護(hù)，

• 因?yàn)?DFS 序一定是連續(xù)的一段（非常繁雜~~~）。

• 注意若查詢的點(diǎn)是葉子結(jié)點(diǎn)（ size 為 1），那么要特判輸出 0，因?yàn)樽约耗Ｗ约簽?0 。

Code

#include<cstdio> using namespace std; const int N=2e5+1; struct tree {int mx,mx1,ymx1,ymx2; }f[N<<2]; struct data {int x,y; }a[N],g[N<<2],null; int tot; int first[N],next[N],en[N]; int dfn[N],size[N],pre[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline int max(int x,int y) {return x>y?x:y; } inline int min(int x,int y) {return x<y?x:y; } inline void insert(int x,int y) {next[++tot]=first[x];first[x]=tot;en[tot]=y; } inline void dfs(int x) {size[x]=1;dfn[x]=++tot;pre[tot]=x;for(int i=first[x];i;i=next[i]){dfs(en[i]);size[x]+=size[en[i]];} } inline tree mergef(tree x,tree y) {tree z;if(x.mx>y.mx){z.mx=x.mx;z.mx1=max(y.mx,x.mx1);z.ymx1=max(y.mx,x.ymx1);z.ymx2=x.ymx2;if(x.ymx1>y.mx) z.ymx2=max(z.ymx2,y.mx);if(x.ymx1<y.mx) z.ymx2=max(z.ymx2,max(x.ymx1,y.ymx1));if(x.ymx1==y.mx) z.ymx2=max(z.ymx2,y.ymx1);}elseif(x.mx<y.mx){z.mx=y.mx;z.mx1=max(x.mx,y.mx1);z.ymx1=max(x.mx,y.ymx1);z.ymx2=y.ymx2;if(y.ymx1>x.mx) z.ymx2=max(z.ymx2,x.mx);if(y.ymx1<x.mx) z.ymx2=max(z.ymx2,max(y.ymx1,x.ymx1));if(y.ymx1==x.mx) z.ymx2=max(z.ymx2,x.ymx1);}else{z.mx=z.mx1=x.mx;z.ymx1=max(x.ymx1,y.ymx1);if(x.ymx1^y.ymx1) z.ymx2=max(x.ymx2,y.ymx2); elsez.ymx2=min(x.ymx1,y.ymx1);}return z; } inline data mergeg(data x,data y) {data z;if(x.x>y.x){z.x=x.x;z.y=max(y.x,x.y);}elseif(x.x<y.x){z.x=y.x;z.y=max(x.x,y.y);}else{z.x=x.x;z.y=max(x.y,y.y);}return z; } inline void make(int v,int l,int r) {if(l==r){f[v].mx=a[pre[l]].x;g[v].x=a[pre[l]].y;return;}int mid=(l+r)>>1,ls=v<<1l,rs=ls|1;make(ls,l,mid);make(rs,mid+1,r);f[v]=mergef(f[ls],f[rs]);g[v]=mergeg(g[ls],g[rs]); } inline tree findf(int v,int l,int r,int x,int y) {if(l>=x && r<=y) return f[v];int mid=(l+r)>>1;if(y<=mid) return findf(v<<1,l,mid,x,y);if(x>mid) return findf(v<<1|1,mid+1,r,x,y);return mergef(findf(v<<1,l,mid,x,mid),findf(v<<1|1,mid+1,r,mid+1,y)); } inline data findg(int v,int l,int r,int x,int y) {if(x>y) return null;if(l>=x && r<=y) return g[v];int mid=(l+r)>>1;if(y<=mid) return findg(v<<1,l,mid,x,y);if(x>mid) return findg(v<<1|1,mid+1,r,x,y);return mergeg(findg(v<<1,l,mid,x,mid),findg(v<<1|1,mid+1,r,mid+1,y)); } int main() {int n=read(),q=read();for(int i=2;i<=n;i++) insert(read(),i);for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();tot=0,dfs(1);make(1,1,n);while(q--){int s=read(),ans=0;if(size[s]==1){puts("0");continue;}tree tx=findf(1,1,n,dfn[s],dfn[s]+size[s]-1);data ty=mergeg(findg(1,1,n,1,dfn[s]-1),findg(1,1,n,dfn[s]+size[s],n));if(tx.mx1+ty.x<tx.mx) ans=tx.mx1+ty.x; elseif(tx.mx1+ty.x>tx.mx) ans=tx.mx; else{if(tx.mx1 && ty.y) ans=tx.mx1+ty.y;if(tx.ymx2 && ty.x) ans=max(ans,tx.ymx2+ty.x);if(tx.ymx1) ans=max(ans,tx.ymx1);}write(ans),putchar('\n');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5460. 【NOIP2017提高A组冲刺11.7】士兵训练的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。