3631: [JLOI2014]松鼠的新家 Time Limit: 10 Sec Memory Limit: 128 MB Description 松鼠的新家是一棵樹，前幾天剛剛裝修了新家，新家有n個房間，并且有n-1根樹枝連接，每個房間都可以相互到達，且倆個房間之間的路線都是唯一的。天哪，他居然真的住在“樹”上。松鼠想邀請小熊維尼前來參觀，并且還指定一份參觀指南，他希望維尼能夠按照他的指南順序，先去a1，再去a2，……，最后到an，去參觀新家。 可是這樣會導致維尼重復走很多房間，懶惰的維尼不聽地推辭。可是松鼠告訴他，每走到一個房間，他就可以從房間拿一塊糖果吃。維尼是個饞家伙，立馬就答應了。 現在松鼠希望知道為了保證維尼有糖果吃，他需要在每一個房間各放至少多少個糖果。因為松鼠參觀指南上的最后一個房間an是餐廳，餐廳里他準備了豐盛的大餐，所以當維尼在參觀的最后到達餐廳時就不需要再拿糖果吃了。 Input 第一行一個整數n，表示房間個數 第二行n個整數，依次描述a1-an 接下來n-1行，每行兩個整數x，y，表示標號x和y的兩個房間之間有樹枝相連。 Output 一共n行，第i行輸出標號為i的房間至少需要放多少個糖果，才能讓維尼有糖果吃。 Sample Input 5 1 4 5 3 2 1 2 2 4 2 3 4 5 Sample Output 1 2 1 2 1 HINT 2<= n <=300000
/*裸樹剖.*/#include<iostream>#include<cstdio>#define MAXN 300001using namespace std;int n,m,tot,cut,maxsize,head[MAXN],a[MAXN],s[MAXN];int size[MAXN],pos[MAXN],top[MAXN],fa[MAXN],deep[MAXN];struct data{int l,r,lc,rc,sum,bj,size;}tree[MAXN<<2];struct edge{int v,next;}e[MAXN<<1];int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f;}void add(int u,int v){ e[++cut].v=v;e[cut].next=head[u];head[u]=cut;}void build(int l,int r){ int k=++tot; tree[k].l=l,tree[k].r=r,tree[k].size=r-l+1; if(l==r) return ; int mid=(l+r)>>1; tree[k].lc=tot+1;build(l,mid); tree[k].rc=tot+1;build(mid+1,r); return ;}void push(int k){ tree[tree[k].lc].bj+=tree[k].bj; tree[tree[k].rc].bj+=tree[k].bj; tree[tree[k].lc].sum+=tree[tree[k].lc].size*tree[k].bj; tree[tree[k].rc].sum+=tree[tree[k].rc].size*tree[k].bj; tree[k].bj=0;return ;}void change(int k,int l,int r,int z){ if(l<=tree[k].l&&tree[k].r<=r) { tree[k].bj+=z;tree[k].sum+=z*tree[k].size; return ; } if(tree[k].bj) push(k); int mid=(tree[k].l+tree[k].r)>>1; if(l<=mid) change(tree[k].lc,l,r,z); if(r>mid) change(tree[k].rc,l,r,z); tree[k].sum=tree[tree[k].lc].sum+tree[tree[k].rc].sum; return ;}int query(int k,int l,int r){ if(l<=tree[k].l&&tree[k].r<=r) return tree[k].sum; if(tree[k].bj) push(k); int mid=(tree[k].l+tree[k].r)>>1,total=0; if(l<=mid) total+=query(tree[k].lc,l,r); if(r>mid) total+=query(tree[k].rc,l,r); return total;}void slove(int k,int l,int r){ if(l==r){s[l]=tree[k].sum;return ;} if(tree[k].bj) push(k); int mid=(l+r)>>1; slove(tree[k].lc,l,mid),slove(tree[k].rc,mid+1,r); return;}void dfs1(int u){ size[u]=1; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(!fa[v]) fa[v]=u,deep[v]=deep[u]+1,dfs1(v),size[v]+=size[u]; } return ;}void dfs2(int u,int top1){ int k=0;pos[u]=++maxsize;top[u]=top1; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(fa[v]==u&&size[v]>size[k]) k=v; } if(!k) return ; dfs2(k,top1); for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(fa[v]==u&&v!=k) dfs2(v,v); } return ;}void slovechange(int x,int y){ change(1,pos[y],pos[y],-1); while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); change(1,pos[top[x]],pos[x],1); x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); change(1,pos[x],pos[y],1);return ;}int main(){ int x,y; n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n-1;i++) x=read(),y=read(),add(x,y),add(y,x); fa[1]=1;dfs1(1),dfs2(1,1),build(1,n); for(int i=1;i<=n-1;i++) slovechange(a[i],a[i+1]); slove(1,1,n); //for(int i=1;i<=n;i++)新聞熱點
疑難解答
