# Noip 2016 tiantianai running

Noip 2016 tiantianai running

It is obvious that the difference on the lca + tree can not be added directly because of the limitation of w, so the combination of weight line segment tree is considered.

It's very troublesome that each player's starting point and ending point have different effects on different nodes. However, it can be found that his depth is fixed in any case. For a node i, he can be + 1 in two situations as follows:

1.dep[x]=dep[i]-w[i]

2.dep[x]=dep[i]+w[i]

So for a group of s, t, find their lca, divide the path into two segments, add 1 to dep[s] of s, subtract 1 from fa[lca], add 1 to 2*dep[lca]-dep[s] of T, and subtract 1 from lca.

Finally, the dfs segment tree is merged. For a node x, query the number of dep[x]-w[x]+dep[x]+w[x] in the corresponding segment tree. Note that if w[x] is 0, divide by 2 (because it is added one more time).

With the experience of "tail in rainy days", the code of this question is still very good.

```#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct edge
{
int u,v,nxt;
#define u(x) ed[x].u
#define v(x) ed[x].v
#define n(x) ed[x].nxt
}ed[300010];
int first[300010],num_e;
#define f(x) first[x]
int n,m,root;
int dep[300010],du[300010];
struct tree
{
int ls,rs,l,r,sum;
#define ls(x)  tr[x].ls
#define rs(x)  tr[x].rs
#define l(x)   tr[x].l
#define r(x)   tr[x].r
#define sum(x) tr[x].sum
}tr[10000010];
int cnt,T[300010];
void add(int &x,int y,int z,int l,int r)
{
if(!x){x=++cnt;l(x)=l,r(x)=r;}
if(l==r){sum(x)+=z;return;}
int mid=(l(x)+r(x))>>1;
sum(x)=0;
if(ls(x))sum(x)+=sum(ls(x));
if(rs(x))sum(x)+=sum(rs(x));
}
int merge(int x,int y,int l,int r)
{
if(!x||!y)return x+y;
if(l==r){sum(x)+=sum(y);return x;}
int mid=(l+r)>>1;
ls(x)=merge(ls(x),ls(y),l,mid);
rs(x)=merge(rs(x),rs(y),mid+1,r);
sum(x)=sum(ls(x))+sum(rs(x));
return x;
}
int ask(int x,int val,int l,int r)
{
if(l==r){return sum(x);}
int mid=(l+r)>>1;
}
int f[300010][21];
int LCA(int x,int y)
{
if(x==y)return x;
if(dep[x]>dep[y])swap(x,y);
while(dep[x]<dep[y])
for(int i=0;;i++)
if(dep[f[y][i]]<dep[x])
{y=f[y][i-1];break;}
if(x==y)return x;
while(f[x][0]!=f[y][0])
for(int i=0;;i++)
if(f[x][i]==f[y][i])
{x=f[x][i-1],y=f[y][i-1];break;}
return f[x][0];
}
void dfs(int x,int de,int fa)
{
dep[x]=de;f[x][0]=fa;
for(int i=f(x);i;i=n(i))
dfs(v(i),de+1,x);
}
int ans[300010],w[300010];
void dfs2(int x)
{
for(int i=f(x);i;i=n(i))
{
dfs2(v(i));
T[x]=merge(T[x],T[v(i)],-n-1,n+1);
}
ans[x]=t1+t2;
if(!w[x])ans[x]-=t1;
}
signed main()
{
//    freopen("in.txt","r",stdin);

scanf("%d%d",&n,&m);
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
}
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
if(!du[i]){root=i;break;}
dfs(root,1,0);
for(int i=1;i<=20;i++)
for(int j=1;j<=n;j++)
f[j][i]=f[f[j][i-1]][i-1];
int s,t;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&s,&t);
int lca=LCA(s,t);
}
dfs2(root);
printf("%d",ans[1]);
for(int i=2;i<=n;i++)
printf(" %d",ans[i]);
}