首页 > 代码库 > NOIP2016 天天爱跑步 正解
NOIP2016 天天爱跑步 正解
暴力移步 http://www.cnblogs.com/TheRoadToTheGold/p/6673430.html
首先解决本题应用的知识点：
dfs序——将求子树的信息（树形）转化为求一段连续区间信息（线形）
线段树——求区间信息
树上差分——统计答案
lca——拆分路径
树链剖分——求lca
另deep[]表示节点的深度，watch[]表示观察者的出现时间，s表示玩家起点，t表示终点
固定节点的观察者出现的时间固定，说明对这个观察者有贡献的点是有限且固定的
只有满足 观察者出现时间=玩家起点与观察者距离的 玩家才对观察者有贡献
每条路径拆成 起点到lca（向上跑） 和 终点到lca的子节点（向下跑） 的两条路径
对于向上跑的，如果玩家能被观察员i观察到，那么deep[s]-deep[i]=watch[i] 式①
对于向下跑的，就是 deep[s]+deep[i]-2*deep[lca(s,i)]=watch[i] 式②
等号左边是玩家起点与观察者的距离，等号右边是观察者出现时间
向上跑的很显然，向下跑的如何理解？
假设我们知道点a，b到lca（a，b）的距离分别为da，db，那么a，b之间的距离=da+db
但这里的deep不是到lca的距离，是深度，即到根节点的距离+1
deep[s]+deep[i]包含2段信息，1、s到i的距离， 2、lca（s，i）到根节点的距离+1
第2段包含了2次，所以减去
先看向上跑的
玩家路径：玩家起点 到 起点与终点的lca
将式①移项，deep[s]=deep[i]+watch[i]
发现等号右边是定值
也就是说对与观察者i，他所能观察到的向上跑的玩家，是所有的起点=deep[i]+watch[i]的玩家
换句话说，以i为根的子树中，所有深度为deep[i]+watch[i]的玩家都能被i观察到
我们如果搞一个dfs序，i的在a时入栈，在b时出栈，
那么以i为根的子树就可以转化为区间[a,b]
深度咋整？
我们对每个深度建立一颗线段树（动态加点）
那么问题就转化为了 在深度为deep[i]+watch[i]的线段树中，查询区间[a,b]的玩家个数
现在就差玩家个数了
很容易想到在起点处+1
但是还要在起点与终点的lca的父节点处-1
差分惯用思想
用sum[]统计这些1和-1的和
那么问题就转化为了 在深度为deep[i]+watch[i]的线段树中，查询区间[a,b]的sum和
提问：为什么是起点处+1，lca的父节点处-1，可以反过来吗？
不可以。
因为起点的深度深，lca的父节点深度浅，在深度深的节点处+1，以深度深度浅的点为根的子树可以包含这个点
想想序列上的差分，是左端点+1，右端点后面的点-1
因为序列差分与前缀和相联系，前面的点的信息对后面的点会产生影响，所以只需加一个1
这里查询的是子树信息，是这个点深度及以下的信息
对照理解即可
向下跑的同理，只简单说怎么做
玩家路径：lca的子节点到玩家终点
把式②移项 deep[s]-2*deep[lca(s,i)]=watch[i]-deep[i]
在watch[i]-deep[i]深度为deep[s]-2*deep[lca(s,i)]的线段树中，终点处+1，lca处-1
查询时查深度为watch[i]-deep[i]的线段树即可
2个小问题：
1、做完向上跑的后，不要忘了清空线段树
2、向下跑的deep[s]-2*deep[lca(s,i)]可能会产生负数，所以全体后移一定长度，root[]数组开大
我后移了2*n，那么root[]数组要开3倍
#include<cstdio>#include<cstring>#include<algorithm>#define N 300401using namespace std;int n,m,fa[N],son[N],deep[N],bl[N],sz,id[N],ans[N];int in[N],out[N],watch[N];int front[N],nextt[N*2],to[N*2];int root[N*3],lc[N*25],rc[N*25],sum[N*25],tot,cnt;struct node{ int s,t,lca;}runner[N];void add(int u,int v){ to[++cnt]=v; nextt[cnt]=front[u]; front[u]=cnt;}void dfs1(int now){ son[now]++; for(int i=front[now];i;i=nextt[i]) { if(to[i]==fa[now]) continue; deep[to[i]]=deep[now]+1; fa[to[i]]=now; dfs1(to[i]); son[now]+=son[to[i]]; }}void dfs2(int now,int chain){ id[now]=++sz; in[now]=sz; bl[now]=chain; int y=0; for(int i=front[now];i;i=nextt[i]) { if(to[i]==fa[now]) continue; if(son[to[i]]>son[y]) y=to[i]; } if(!y) { out[now]=sz; return; } dfs2(y,chain); for(int i=front[now];i;i=nextt[i]) { if(to[i]==fa[now]||to[i]==y) continue; dfs2(to[i],to[i]); } out[now]=sz;}int getlca(int u,int v){ while(bl[u]!=bl[v]) { if(deep[bl[u]]<deep[bl[v]]) swap(u,v); u=fa[bl[u]]; } return deep[u]<deep[v] ? u:v;}void change(int & now,int l,int r,int pos,int w){ if(!pos) return; if(!now) now=++tot; sum[now]+=w; if(l==r) return; int mid=l+r>>1; if(pos<=mid) change(lc[now],l,mid,pos,w); else change(rc[now],mid+1,r,pos,w);}int query(int now,int l,int r,int opl,int opr){ if(!now) return 0; if(l==opl&&r==opr) return sum[now]; int mid=l+r>>1; if(opr<=mid) return query(lc[now],l,mid,opl,opr); else if(opl>mid) return query(rc[now],mid+1,r,opl,opr); else return query(lc[now],l,mid,opl,mid)+query(rc[now],mid+1,r,mid+1,opr);}void clear(){ tot=0; memset(lc,0,sizeof(lc)); memset(rc,0,sizeof(rc)); memset(sum,0,sizeof(sum)); memset(root,0,sizeof(root));}int main(){ /*freopen("runninga.in","r",stdin); freopen("runninga.out","w",stdout);*/ scanf("%d%d",&n,&m); int u,v; for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); add(u,v);add(v,u); } for(int i=1;i<=n;i++) scanf("%d",&watch[i]); for(int i=1;i<=m;i++) scanf("%d%d",&runner[i].s,&runner[i].t); dfs1(1); dfs2(1,0); for(int i=1;i<=m;i++) runner[i].lca=getlca(runner[i].s,runner[i].t); int now; for(int i=1;i<=m;i++) { now=deep[runner[i].s]; change(root[now],1,n,id[runner[i].s],1); change(root[now],1,n,id[fa[runner[i].lca]],-1); } for(int i=1;i<=n;i++) ans[i]=query(root[deep[i]+watch[i]],1,n,in[i],out[i]); clear(); for(int i=1;i<=m;i++) { now=deep[runner[i].s]-deep[runner[i].lca]*2+n*2; change(root[now],1,n,id[runner[i].t],1); change(root[now],1,n,id[runner[i].lca],-1); } for(int i=1;i<=n;i++) ans[i]+=query(root[watch[i]-deep[i]+n*2],1,n,in[i],out[i]); for(int i=1;i<=n;i++) printf("%d ",ans[i]);}
NOIP2016 天天爱跑步 正解