洛谷-3258 [JLOI2014]松鼠的新家

题目描述 松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。 松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去$a_1$，再去$a_2$，…，最后到$a_n$，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。 维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。 因为松鼠参观指南上的最后一个房间$a_n$是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。 输入格式 第一行一个整数n，表示房间个数第二行n个整数，依次描述$a_1-a_n$ 接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。 输出格式 一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。

输入输出样例 输入 #1 5 1 4 5 3 2 1 2 2 4 2 3 4 5

输出 #1 1 2 1 2 1

说明/提示 2<= n <=300000

解释：树链剖分的模板题，我们把$[a_i,a_{i+1}]$经过的节点全部加1，最后我们再对每个$a_2,...a_n$-1，因为我们重复加了一次，直接得到答案

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define lson rt<<1 #define rson rt<<1|1 #define ll long long const ll N=300003; const ll inf=-100000009; using namespace std; ll n,idx,dfn[N],seq[N],fa[N],dep[N],top[N],sz[N],hvy[N]; ll tree[8*N]={0},val[N]={0}; ll a[N]={0}; ll lazy[8*N]={0}; ll tot,lnk[N],ter[4*N],nxt[4*N]; void add(ll u,ll v){ ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot; } void dfs1(ll u,ll f) { fa[u]=f,dep[u]=dep[f]+1,sz[u]=1,hvy[u]=top[u]=0; for(ll i=lnk[u];i;i=nxt[i]) { ll v=ter[i]; if(v==f) continue; dfs1(v,u); sz[u]+=sz[v]; if(sz[hvy[u]]<sz[v]) hvy[u]=v; } } void dfs2(ll u,ll tp) { dfn[u]=++idx,seq[idx]=u,top[u]=tp; if(!hvy[u]) return; dfs2(hvy[u],tp); for(ll i=lnk[u];i;i=nxt[i]) { ll v=ter[i]; if(v==fa[u]||v==hvy[u]) continue; dfs2(v,v); } } void pushup(ll rt) { tree[rt]=tree[lson]+tree[rson]; } void pushdown(ll rt,ll l,ll r){ ll mid=(l+r)/2; tree[lson]+=lazy[rt]*(mid-l+1); tree[rson]+=lazy[rt]*(r-mid); lazy[lson]+=lazy[rt]; lazy[rson]+=lazy[rt]; lazy[rt]=0; return; } void build(ll rt,ll l,ll r) { if(l==r) { tree[rt]=val[seq[l]]; return; } ll mid=(l+r)>>1; build(lson,l,mid); build(rson,mid+1,r); pushup(rt); } void modify(ll L,ll R,ll rt,ll l,ll r,ll val) { pushdown(rt,l,r); if(L<=l&&r<=R){ tree[rt]+=val*(r-l+1); lazy[rt]+=val; return; } ll mid=(l+r)>>1; if(L<=mid) modify(L,R,lson,l,mid,val); if(R>mid) modify(L,R,rson,mid+1,r,val); pushup(rt); } void chainmodify(ll u,ll v) { for(ll fu=top[u],fv=top[v];fu^fv;u=fa[fu],fu=top[u]){ if(dep[fu]<dep[fv]) swap(u,v),swap(fu,fv); modify(dfn[fu],dfn[u],1,1,n,1LL); } if(dep[u]>dep[v]) swap(u,v); modify(dfn[u],dfn[v],1,1,n,1LL); return ; } ll query(ll x,ll rt,ll l,ll r){ pushdown(rt,l,r); if(l==r) return tree[rt]; ll mid=(l+r)>>1; if(x<=mid) return query(x,lson,l,mid); if(mid<x) return query(x,rson,mid+1,r); return 0; } ll ans[N]={0}; int main(){ scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<n;++i){ ll u,v; scanf("%lld%lld",&u,&v); add(u,v),add(v,u); } dfs1(1,0),dfs2(1,1),build(1,1,n); for(int i=2;i<=n;i++) chainmodify(a[i-1],a[i]); for(int i=1;i<=n;i++) ans[i]=query(dfn[i],1,1,n); for(int i=2;i<=n;i++) ans[a[i]]--; for(int i=1;i<=n;i++) printf("%lld\n",ans[i]); return 0; }