NOIP 2016 天天愛跑步
洛谷傳送門
JDOJ傳送門
Description
Input
Output
Sample Input
6 3 2 3 1 2 1 4 4 5 4 6 0 2 5 1 2 3 1 5 1 3 2 6
Sample Output
2 0 0 1 1 1
HINT
題解：
先口胡一下部分分。
首先1号、2号，隻有0時刻出現的觀察員能夠看到人，所有人都在0時刻出現。那麼樹上差分統計人數即可。
3号、4号，也是隻有0時刻觀察員，隻統計起點即可。
5号，暴力可過。
9-12号，由于起點固定，是以每個人跑到每個點的時間可以用性質算出來，然後按這個性質統計即可。
13-16号同理。
那麼再考慮正解。
9-12和13-16号點可以給我們很大的啟發：我們發現針對起點為1、終點為1的路徑，都是按性質走的，是以我們就可以得到一個啟發：将一條路徑拆分成兩個支路來解決。這樣的話，這樣的兩條之路可以分别利用性質來處理。
這個性質是：在上行路徑上，滿足
\[deep[s]-deep[x]=t[x]
\]
這樣的點是對答案有貢獻的。
在下行路徑上，滿足
\[deep[s]+deep[x]-2\times deep[lca]=t[x]
那麼對于每一個節點\(x\)，根據以上性質，就有\(deep[s]=deep[x]+t[x]\)，也就是說，對于一條起點為s的上行路徑來講，它會對這個路徑上所有滿足這個性質的點作貢獻。
下行路徑同理。
那麼怎麼處理呢？思路到這裡，權值線段樹的想法就比較自然了。按起始節點s的深度deep[s]來統計人數。是以我們可以考慮用權值線段樹（動态開點）來維護這個資訊。然後通過樹上差分快速處理新路徑。最後隻需要從下到上線段樹合并統計即可。
注意，上行和下行要統計兩遍。
代碼：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
int x=0,f=1;
char ch=nc();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=nc();
}
while(ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=nc();
return x*f;
}
const int maxn=3*1e5+10;
int n,m,maxx;
int tot,to[maxn<<1],nxt[maxn<<1],head[maxn];
int t[maxn];
int top[maxn],fa[maxn],deep[maxn],size[maxn],son[maxn];
int b[maxn],e[maxn],lcaa[maxn];
int sum[maxn*50],lson[maxn*50],rson[maxn*50],cnt;
int root[maxn],ans[maxn];
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs1(int x,int f)
{
deep[x]=deep[f]+1;
fa[x]=f;
size[x]=1;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f)
continue;
dfs1(y,x);
size[x]+=size[y];
if(!son[x]||size[y]>size[son[x]])
son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
if(!son[x])
return;
dfs2(son[x],t);
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==fa[x]||y==son[x])
continue;
dfs2(y,y);
}
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
swap(x,y);
x=fa[top[x]];
}
return deep[x]<deep[y]?x:y;
}
void pushup(int pos)
{
sum[pos]=sum[lson[pos]]+sum[rson[pos]];
}
void update(int &pos,int l,int r,int x,int k)
{
int mid=(l+r)>>1;
if(!pos)
pos=++cnt;
if(l==r)
{
sum[pos]+=k;
return;
}
if(x<=mid)
update(lson[pos],l,mid,x,k);
else
update(rson[pos],mid+1,r,x,k);
pushup(pos);
}
int query(int pos,int l,int r,int x)
{
int mid=(l+r)>>1;
if(l==r)
return sum[pos];
if(x<=mid)
return query(lson[pos],l,mid,x);
else
return query(rson[pos],mid+1,r,x);
}
void merge(int &x,int y,int l,int r)
{
int mid=(l+r)>>1;
if(!x||!y)
{
x=(!x?y:x);
return;
}
if(l==r)
sum[x]+=sum[y];
merge(lson[x],lson[y],l,mid);
merge(rson[x],rson[y],mid+1,r);
}
void dfs3(int x)
{
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==fa[x])
continue;
dfs3(y);
merge(root[x],root[y],1,maxx);
}
if(n+deep[x]+t[x]<=maxx)
ans[x]+=query(root[x],1,maxx,n+deep[x]+t[x]);
}
void dfs4(int x)
{
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==fa[x])
continue;
dfs4(y);
merge(root[x],root[y],1,maxx);
}
ans[x]+=query(root[x],1,maxx,n+deep[x]-t[x]);
}
int main()
{
n=read();m=read();
for(int i=1;i<n;i++)
{
int x,y;
x=read();y=read();
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
t[i]=read();
dfs1(1,0);
dfs2(1,1);
maxx=n<<1;
for(int i=1;i<=m;i++)
{
b[i]=read(),e[i]=read();
lcaa[i]=lca(b[i],e[i]);
update(root[b[i]],1,maxx,deep[b[i]]+n,1);
update(root[fa[lcaa[i]]],1,maxx,deep[b[i]]+n,-1);
}
dfs3(1);
cnt=0;
memset(root,0,sizeof(root));
memset(sum,0,sizeof(sum));
memset(lson,0,sizeof(lson));
memset(rson,0,sizeof(rson));
for(int i=1;i<=m;i++)
{
update(root[e[i]],1,maxx,n-deep[b[i]]+2*deep[lcaa[i]],1);
update(root[lcaa[i]],1,maxx,n-deep[b[i]]+2*deep[lcaa[i]],-1);
}
dfs4(1);
for(int i=1;i<n;i++)
printf("%d ",ans[i]);
printf("%d",ans[n]);
return 0;
}