---

题面:

B【NOIP2016 DAY1】天天爱跑步

时间限制 : - MS 空间限制 : 565536 KB 评测说明 : 2s

Description

小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要

玩家每天按时上线,完成打卡任务。这个游戏的地图可以看作一一棵包含 \(N\)个结点和\(N-1\) 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从1到N的连续正整数。现在有个玩家,第个玩家的起点为\(Si\) ,终点为\(Ti\) 。每天打卡任务开始时,所有玩家在第\(0\)秒同时从自己的起点出发, 以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。

(由于地图是一棵树, 所以每个人的路径是唯一的)小C想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。 在结点的观察员会选择在第\(W_j\)秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第\(W_j\)秒也理到达了结点\(J\)。

小C想知道每个观察员会观察到多少人?注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一 段时间后再被观察员观察到。 即对于把结点\(J\)作为终点的玩家: 若他在第\(W_j\)秒重到达终点,则在结点\(J\)的观察员不能观察到该玩家;若他正好在第\(W_j\)秒到达终点,则在结点的观察员可以观察到这个玩家。

Input

第一行有两个整数\(N\)和\(M\) 。其中\(N\)代表树的结点数量, 同时也是观察员的数量, \(M\)代表玩家的数量。

接下来\(n-1\) 行每行两个整数\(U\)和\(V\) ,表示结点\(U\)到结点\(V\)有一条边。

接下来一行\(N\) 个整数,其中第个整数为\(W_j\), 表示结点出现观察员的时间。

接下来 \(M\)行,每行两个整数\(S_i\)和\(T_i\)表示一个玩家的起点和终点。

对于所有的数据,保证 。

\(1<=S_i,T_i<=N,0<=W_j<=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\)号点，\(W_1=0\)，故只有起点为\(1\)号点的玩家才会被观察到，所以玩家\(1\)和玩家\(2\)被观察到，共\(2\)人被观察到。

对于\(2\)号点，没有玩家在第\(2\)秒时在此结点，共\(0\)人被观察到。

对于\(3\)号点，没有玩家在第\(5\)秒时在此结点，共\(0\)人被观察到。

对于\(4\)号点，玩家\(1\)被观察到，共\(1\)人被观察到。

对于\(5\)号点，玩家\(1\)被观察到，共\(1\)人被观察到。

对于\(6\)号点，玩家\(3\)被观察到，共\(1\)人被观察到

---

题解:

为了这道题还专门去学习了线段树合并(暴露了蒟蒻现在才会这东西的事实),有空也会写一篇关于线段树合并的博客,这篇博客将不对其原理进行解释(这都挖了几个坑了啊)(ps:已秒填坑)

我们考虑对一个节点\(i\)的子树中如果含有起点\(x\),我们很容易得到这样的式子:\(dep[x]-dep[i]==w[i]\),(\(w[i]\)是这个节点观察员出现的时间),我们一般希望将等式两边处理为一个相对的定值(不知道怎么表达这种感觉,意会意会),推出\(dep[i]+w[i]==dep[x]\),对于这个式子,左边对观察者就是定值,右边对于跑步者就是定值;

同样,当终点\(x\)在节点\(i\)的子树里时,我们需要将时间的影响考虑进去,记起点与中点的距离为\(dis\),那么\(w[i]==dep[i]-dep[x]+dis\),移项变为\(w[i]-dep[i]==dis-dep[x]\),对这个式子来说,依旧是:左边对观察者是定值,右边对于跑步者是定值;

\(Start:dep[i]+w[i]==dep[Start]\)

\(End:w[i]-dep[i]==dis-dep[End]\)

于是我们的问题就转换为求一颗子树中,对这个子树的根所能做的贡献之和,即求子树中满足根节点为\(i\)时的节点个数(当然这个节点可能会同时有几个权值);

于是,我们考虑对每一个点维护权值线段树(每个点维护两个,分别记录起点终点),表示自己所包含子树中所含的每个值的点个数为多少;

考虑使用树剖的思想,将起点到终点的过程分解为从起点到\(LCA\),从\(LCA\)到终点这两条链,这时候我们就可以显然的使用差分的思想;

在起点的起点树(对一个点开两个线段树,记记录起点的叫起点树,另一个为终点树)的\(dep[Start]\)的位置\(+1\),\(Father_LCA\)的\(dep[Start]\)位置的起点树\(-1\);

在终点终点树\(dis-dep[End]\)的位置\(+1\),在\(LCA\)的\(dis-dep[End]\)的位置\(-1\),这就是对序列差分的原理;

\(DFS\)统计答案,从叶节点开始,统计完就向上合并即可;

注意权值线段树可能出现负数,需要偏移;

\(code:\)

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;char buf[1<<20],*p1,*p2;inline char gc(){//    return getchar();    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;}template
        
         inline void read(T &x){    char tt;    bool flag=0;    while(!isdigit(tt=gc())&&tt!='-');    tt=='-'?(flag=1,x=0):(x=tt-'0');    while(isdigit(tt=gc())) x=x*10+tt-'0';    if(flag) x=-x;}const int maxn=3*(1e5+2);int sum[maxn*40][2],ls[maxn*40][2],rs[maxn*40][2],tot[2],root[maxn*40][2];int n,m,w[maxn],mx,ans[maxn];int son[maxn],top[maxn],sz[maxn],dep[maxn],fa[maxn];vector
         
          G[maxn];int getlca(int x,int y){ if(x==y) return x; while(top[x]^top[y]) dep[top[x]]>=dep[top[y]]?x=fa[top[x]]:y=fa[top[y]]; return dep[x]<=dep[y]?x:y;}int cal(int x,int y,int lca){ return dep[x]+dep[y]-(dep[lca]<<1);}void modify(int &p,int l,int r,int x,int d,int id){ if(!p) p=++tot[id]; if(l==r){sum[p][id]+=d;return;} int mid=l+r>>1; if(x<=mid) modify(ls[p][id],l,mid,x,d,id); if(x>mid) modify(rs[p][id],mid+1,r,x,d,id);}int query(int &p,int l,int r,int x,int id){ if(!p) p=++tot[id]; if(l==r){return sum[p][id];} int mid=l+r>>1; if(x<=mid) return query(ls[p][id],l,mid,x,id); if(x>mid) return query(rs[p][id],mid+1,r,x,id);}void merge(int &x,int y,int id){ if(!x||!y){x=x+y;return;} sum[x][id]+=sum[y][id]; merge(ls[x][id],ls[y][id],id); merge(rs[x][id],rs[y][id],id);}void dfs(int x,int pre){ sz[x]++,dep[x]=dep[pre]+1,fa[x]=pre; for(int i=G[x].size()-1;i>=0;i--) { int p=G[x][i]; if(p==pre) continue; dfs(p,x); if(sz[p]>sz[son[x]]) son[x]=p; sz[x]+=sz[p]; }}void dfs(int x,int pre,int t){ top[x]=t; if(!son[x]) return; dfs(son[x],x,t); for(int i=G[x].size()-1;i>=0;i--) { int p=G[x][i]; if(p==pre||p==son[x]) continue; dfs(p,x,p); }}void dfs(int x){ for(int i=G[x].size()-1;i>=0;i--) { int p=G[x][i]; if(p==fa[x]) continue; dfs(p); merge(root[x][0],root[p][0],0); merge(root[x][1],root[p][1],1); } ans[x]+=query(root[x][0],1,mx,dep[x]+w[x],0); ans[x]+=query(root[x][1],1,mx,w[x]-dep[x]+maxn,1);}int main(){ read(n),read(m);mx=n+maxn; for(int i=1;i