NOIP2016天天爱跑步

　　　　　　　　　　2557. [NOIP2016]天天爱跑步

时间限制：2 s 内存限制：512 MB

【题目描述】

小C同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一棵包含n个结点和n-1条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从1到n的连续正整数。

现在有m个玩家，第i个玩家的起点为Si，终点为Ti。每天打卡任务开始时，所有玩家在第0秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）

小C想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。在结点的观察员会选择在第Wj秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第Wj秒也理到达了结点J 。小C想知道每个观察员会观察到多少人?

注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一段时间后再被观察员观察到。即对于把结点J作为终点的玩家: 若他在第Wj秒重到达终点,则在结点J的观察员不能观察到该玩家;若他正好在第Wj秒到达终点,则在结点的观察员可以观察到这个玩家。

【输入格式】

第一行有两个整数n和m。其中n代表树的结点数量，同时也是观察员的数量，m代表玩家的数量。

接下来n-1行每行两个整数u和v，表示结点u到结点v有一条边。

接下来一行n个整数，其中第j个整数为Wj，表示结点j出现观察员的时间。

接下来m行,每行两个整数Si和Ti，表示一个玩家的起点和终点。

对于所有的数据，保证1≤Si,Ti≤n，0≤ Wj ≤n。

【输出格式】

输出1行n个整数,第j个整数表示结点j的观察员可以观察到多少人。

【样例1输入】

6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6

【样例1输出】

2 0 0 1 1 1

【样例2输入】

5 3

1 2

2 3

2 4

1 5

0 1 0 3 0

3 1

1 4

5 5

【样例2输出】

1 2 1 0 1

【提示】

对于1号点，W1=0，故只有起点为1号点的玩家才会被观察到，所以玩家1和玩家2被观察到，共2人被观察到。

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

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

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

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

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

　　感觉这是一道好难的题，，别人花10分钟打dfs拿了暴力25分，我花了快一个小时打树链刨分维护线段树也才拿了25分呜呜呜~~~~(>_<)~~~~

上网搜别人的题解发现都讲得懵懵懂懂的，反正自己是理解了好半天的呢！

　　我答的应该还是一些比较容易懂的方法吧..

解题报告：：

　　　　发现数据n,m都是30W以上的，果断确定算法O(nlogn) ,而且只能选择一个，要么处理人，要么处理观察员，我们在这里用一下经典思路：两个节点S,T之间的距离，可以把它看成从S到lca（最近公共祖先），从lca再到T的过程，对这两部分过程进行分段处理就好了。

　　　　①：从S到lca的过程中，一个观察员i如果能够观察到跑步人x的话，那一定满足式子dp[x]-dp[i]==w[i]（dp是深度，w是时间，因为根节点的深度为0，并且每一条边的长度都为一，所以dp数组也可以看成是到根节点的距离）,我们对他进行一下移项处理：dp[x]=dp[i]+w[i],可以发现等式的右边是一个定值，所以这时候就比较容易想到了，我们对跑步的人进行处理，询问时查询每一个节点的dp[i]+w[i]即可。首先用树链剖分预处理出dp数组，求出每个人起点和终点的lca；然后进行动态插点，因为询问时，如果观察员能观察到这个人，那么dp[i]+w[i]一定等于dp[x]，并且观察到同一个人的所有观察员肯定满足dp[i]+w[i]==dp[j]+w[j];所以我们对每一个深度dp[S]进行插入,如何解决内存的问题呢？？用线段树的动态开点就好了，

　　　　②：返回来同理：dp[i]+dp[S]-2*dp[lca]=w[i],进行移项处理：dp[S]-2*dp[lca]==w[i]-dp[i];原理同上，但因为是减法，会出负数，所以整体右移，这就会使内存很大很大，开数组的时候一定要注意，我在这里跪了几次(⊙o⊙)…，在处理完第一个时候，用一个数组存储答案，然后先前的那些就没有用了，反而会对后面的产生干扰，所以在求第二次的时候，不要忘记清空线段树，还有个细节要注意，因为lca是只经过一次的，但是你两个路径中却都有，所以你要舍一个，用fa[lca]来当上界了。

　　补充：因为一个观察员能观察到人当且仅当这个人的路线是经过观察员的，所以插入的时候要用到差分和dfs序的思想，一个点在进入时有一个时间戳，出来是有一个时间戳，那么在插入操作时，以第一段为例，只要在起点的时间戳出+1，再其fa[lca]处-1(包含lca)，这样如果这个人是经过观察员的，那么观察员进出的时间戳中就构成了一个连续的区间，这个区间中一定会有起点的那个+1，没有lca的-1，如果没有经过，要么是区间中不含+1，或者是+1与-1抵消了，这样都不会产生任何影响的；、

　　　　所以最后对每个节点的观察员来说，答案即为在dp[i]+w[i]询问其子树中的数量+第二次w[i]-dp[i]+2*n(为了防止出负数，整体右移了2*n,数组也要相应的扩大更多)询问其子树中的数量之和

输出答案即可

　　总结：这道题真的好难想啊，树链剖分求lca+树上差分+动态开点线段树+最最难想到的那个式子

╮(╯▽╰)╭貌似这道题可用DP和DFS两种方法水过？？（这个方法才叫水吧）。

　　附码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 int n,m,num,x,y,dex;
  7 int w[300000],adj[300000];
  8 int rt[7000000],lc[7000000],rc[7000000];
  9 struct edge{
 10     int s,t,next;
 11 }k[600000];
 12 struct sta{
 13     int s,t,lca;
 14 }l[300000];
 15 int read(){
 16     int sum=0;char ch=getchar();
 17     while(ch<'0'||ch>'9') ch=getchar();
 18     while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
 19     return sum;
 20 }
 21 void init(int s,int t){
 22     k[num].s=s;k[num].t=t;
 23     k[num].next=adj[s];adj[s]=num++;
 24     k[num].s=t;k[num].t=s;
 25     k[num].next=adj[t];adj[t]=num++;
 26 }
 27 int fa[300000],dp[300000],son[300000],size[300000];
 28 void Dfs1(int x){
 29     son[x]=0;size[x]=1;
 30     for(int i=adj[x];i!=-1;i=k[i].next){
 31         int o=k[i].t;
 32         if(o!=fa[x]){
 33             fa[o]=x;dp[o]=dp[x]+1;
 34             Dfs1(o);
 35             size[x]+=size[o];
 36             if(size[son[x]]<size[o])
 37                 son[x]=o;
 38         }
 39     }
 40 }
 41 int pos[300000],id[300000],top[300000],qiong[300000],cnt;
 42 void Dfs2(int u,int tp){
 43     pos[++cnt]=u;id[u]=cnt;
 44     top[u]=tp;
 45     if(son[u]) Dfs2(son[u],tp);
 46     for(int i=adj[u];i!=-1;i=k[i].next){
 47         int o=k[i].t;
 48         if(o!=fa[u]&&o!=son[u])
 49             Dfs2(o,o);
 50     }
 51     qiong[u]=cnt;
 52 }
 53 int LCA(int x,int y){
 54     int fx=top[x],fy=top[y];
 55     while(fx^fy){
 56         if(dp[fx]<dp[fy]){
 57             swap(fx,fy);
 58             swap(x,y);
 59         }
 60         x=fa[fx];fx=top[x];
 61     }
 62     return dp[x]<dp[y]?x:y;
 63 }
 64 int sum[7700000];
 65 void change(int x,int z,int l,int r,int &now){
 66     if(!x) return;
 67     if(!now) now=++dex;
 68     sum[now]+=z;
 69     if(l==r) return;
 70     int mid=(l+r)>>1;
 71     if(x<=mid) change(x,z,l,mid,lc[now]);
 72     else change(x,z,mid+1,r,rc[now]);
 73 }
 74 int query(int s,int t,int l,int r,int rt){
 75     if(!rt) return 0;
 76     if(s<=l&&r<=t) return sum[rt];
 77     int mid=(l+r)>>1;
 78     int ans=0;
 79     if(s<=mid) ans+=query(s,t,l,mid,lc[rt]);
 80     if(t>mid) ans+=query(s,t,mid+1,r,rc[rt]);
 81     return ans;
 82 }
 83 void clear(){
 84     dex=0;
 85     memset(lc,0,sizeof(lc));
 86     memset(rc,0,sizeof(rc));
 87     memset(sum,0,sizeof(sum));
 88     memset(rt,0,sizeof(rt));
 89 }
 90 int ans[300000];
 91 int main(){
 92     //freopen("runninga.in","r",stdin);
 93     //freopen("runninga.out","w",stdout);
 94     memset(adj,-1,sizeof(adj));
 95     n=read();m=read();
 96     for(int i=1;i<n;++i){
 97         x=read();y=read();
 98         init(x,y);
 99     }
100     for(int i=1;i<=n;++i)
101         w[i]=read();
102     Dfs1(1);Dfs2(1,1);
103     for(int i=1;i<=m;++i)
104         l[i].s=read(),l[i].t=read(),l[i].lca=LCA(l[i].s,l[i].t);
105     for(int i=1;i<=m;++i){
106         int now=dp[l[i].s];
107         change(id[l[i].s],1,1,n,rt[now]);
108         change(id[fa[l[i].lca]],-1,1,n,rt[now]);
109     }
110     for(int i=1;i<=n;++i)
111         ans[i]=query(id[i],qiong[i],1,n,rt[dp[i]+w[i]]);
112     clear();
113     for(int i=1;i<=m;++i){
114         int now=dp[l[i].s]-2*dp[l[i].lca]+2*n;
115         change(id[l[i].t],1,1,n,rt[now]);
116         change(id[l[i].lca],-1,1,n,rt[now]);
117     }
118     for(int i=1;i<=n;++i)
119         ans[i]+=query(id[i],qiong[i],1,n,rt[w[i]-dp[i]+2*n]);
120     for(int i=1;i<=n;++i)
121         printf("%d ",ans[i]);
122     return 0;
123 }