Description
小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。?天天爱跑步?是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。这个游戏的地图可以看作一一棵包含 N个结点和N-1 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从1到N的连续正整数。现在有个玩家,第个玩家的起点为Si ,终点为Ti 。每天打卡任务开始时,所有玩家在第0秒同时从自己的起点出发, 以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树, 所以每个人的路径是唯一的)小C想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。 在结点的观察员会选择在第Wj秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第Wj秒也理到达了结点J 。 小C想知道每个观察员会观察到多少人?注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一 段时间后再被观察员观察到。 即对于把结点J作为终点的玩家: 若他在第Wj秒重到达终点,则在结点J的观察员不能观察到该玩家;若他正好在第Wj秒到达终点,则在结点的观察员可以观察到这个玩家。
Input
第一行有两个整数N和M 。其中N代表树的结点数量, 同时也是观察员的数量, M代表玩家的数量。
接下来n-1 行每行两个整数U和V ,表示结点U 到结点V 有一条边。
接下来一行N 个整数,其中第个整数为Wj , 表示结点出现观察员的时间。
接下来 M行,每行两个整数Si和Ti,表示一个玩家的起点和终点。
对于所有的数据,保证 。
1<=Si,Ti<=N,0<=Wj<=N
**Output
输出1行N 个整数,第个整数表示结点的观察员可以观察到多少人。
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号点，W1=0，故只有起点为1号点的玩家才会被观察到，所以玩家1和玩家2被观察到，共2人被观察到。
对于2号点，没有玩家在第2秒时在此结点，共0人被观察到。
对于3号点，没有玩家在第5秒时在此结点，共0人被观察到。
对于4号点，玩家1被观察到，共1人被观察到。
对于5号点，玩家1被观察到，共1人被观察到。
对于6号点，玩家3被观察到，共1人被观察到
Solution
线段树合并，类似于树形dp的方法。
对于一个点x，我们要找的路径有两种情况：一种是在x的子树中出发，在x的子树之外结束；另一种是从x的子树外出发，进入x的子树中结束。我们可以把信息记在路径的开始和结束点上，这样在从子树往上合并信息的时候就可以统计路径。
用 depthx 表示x的深度，用 valx 表示x的权值（即观察的时间）。
第一种情况下，设路径的起点为u。如果路径u能被x观察到，那么必须满足 depthu?depthx=valx ，即 depthu=valx+depthx 。所以我们可以用线段树维护子树信息，对于每个是起点的点把 depthu 插到线段树中，在dfs返回到x时，x的各个子树信息必定已经统计完成，我们就把返回的这些线段树合并起来，然后查找线段树中等于 valx+depthx 的元素个数，这就是从子树中到达x点的合法路径条数。
第二种情况下，设路径的起点为u，终点为v，路径起点、终点的lca为p，那么如果合法就有 depthx?depthp+depu?depp=valx ，
移项后得 valx?depthx=depu?2?depthp ，所以对于每个是终点的点将 depu?2?depthp 插入另一棵线段树中，然后查找等于 valx?depthx 的元素个数即为第二种情况的答案。注意 valx?depthx 可能为负，所以我们可以统一加上n。
还有就是路径在lca处的处理。如果x在某条路径的lca处，那么这个点返回的线段树中就不能包含这条路径的信息，因为它不可能经过这个节点的祖先了，所以要把他删除。同时这种路径的信息将会同时包含于前面两种情况中，所以两棵线段树中都要删除，而且统计的时候必须是先统计一种，然后把这种路径删除，再统计第二种，这样才能不重不漏。
代码：
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;template<typename T>inline void read(T &x){T f=1;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';x*=f;
}const int maxn=300010,max0=19;
struct edge{int to,nxt;
}e[maxn<<2];
struct node{int size;struct node *lc,*rc;node():lc(NULL),rc(NULL),size(0){}
};
struct Path{int beg,end,lca;
}p[maxn];
typedef node* Node;
int n,m,num,head[maxn],t[maxn],tag[maxn];
int fa[maxn][20],dep[maxn],ans[maxn];
vector<int>b[maxn],c[maxn];void add(int u,int v){e[++num].to=v;e[num].nxt=head[u];head[u]=num;e[++num].to=u;e[num].nxt=head[v];head[v]=num;
}
void Init(int x,int f){dep[x]=dep[fa[x][0]=f]+1;for(int i=1;i<=max0;i++)if(fa[x][i-1])fa[x][i]=fa[fa[x][i-1]][i-1];else break;for(int i=head[x];i;i=e[i].nxt)if(e[i].to!=f)Init(e[i].to,x);
}
int lca(int u,int v){if(dep[u]<dep[v])swap(u,v);int delta=dep[u]-dep[v];for(int i=0;i<=max0;i++)if(delta&(1<<i))u=fa[u][i];if(u==v)return u;for(int i=max0;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];return fa[u][0];
}
void Insert(Node &x,int l,int r,int val,int t=1){if(x==NULL)x=new node;x->size+=t;if(l==r)return;int mid=(l+r)>>1;if(val<=mid)Insert(x->lc,l,mid,val,t);else Insert(x->rc,mid+1,r,val,t);
}
void del(Node &x){delete x;x=NULL;
}
void Delete(Node &x,int l,int r,int val){x->size--;if(l==r){if(!x->size)del(x);return;}int mid=(l+r)>>1;if(val<=mid)Delete(x->lc,l,mid,val);else Delete(x->rc,mid+1,r,val);if(!x->size)del(x);
}
int Query(Node x,int l,int r,int val){if(x==NULL)return 0;if(l==r)return x->size;int mid=(l+r)>>1;if(val<=mid)return Query(x->lc,l,mid,val);else return Query(x->rc,mid+1,r,val);
}
Node Merge(Node &x,Node &y){if(!x||!y){if(!x&&!y)return NULL;return !x?y:x;}Node res=new node;res->size=x->size+y->size;res->lc=Merge(x->lc,y->lc);res->rc=Merge(x->rc,y->rc);del(x);del(y);return res;
}
pair<Node,Node> Dfs(int x){pair<Node,Node>now,temp;for(int i=head[x];i;i=e[i].nxt){if(e[i].to==fa[x][0])continue;temp=Dfs(e[i].to);now.first=Merge(now.first,temp.first);now.second=Merge(now.second,temp.second);}if(tag[x])Insert(now.first,1,n<<1,dep[x],tag[x]);for(auto i=b[x].begin();i!=b[x].end();i++)Insert(now.second,1,n<<1,dep[p[*i].beg]-2*dep[p[*i].lca]+n+1);ans[x]+=Query(now.first,1,n<<1,t[x]+dep[x]);for(auto i=c[x].begin();i!=c[x].end();i++){Delete(now.first,1,n<<1,dep[p[*i].beg]);Delete(now.second,1,n<<1,dep[p[*i].beg]-2*dep[p[*i].lca]+n+1);}ans[x]+=Query(now.second,1,n<<1,t[x]-dep[x]+n+1);return now;
}int main(){read(n);read(m);for(int i=1,u,v;i<n;i++){read(u);read(v);add(u,v);}Init(1,0);for(int i=1;i<=n;i++)read(t[i]);for(int i=1,beg,end;i<=m;i++){read(beg);read(end);p[i].beg=beg;p[i].end=end;tag[beg]++;b[end].push_back(i);c[p[i].lca=lca(beg,end)].push_back(i);}Dfs(1);for(int i=1;i<=n;i++)printf("%d ",ans[i]);return putchar(10),0;
}