NOIP2016 天天爱跑步 线段树合并

题意：

　　给出一棵n个点的树，以及m次操作，每次操作从起点向终点以每秒一条边的速度移动（初始时刻为0），最后对于每个点询问有多少次操作在经过该点的时刻为某值。

　　（题面太毒瘤建议自己去题库食用）

 

分析：

　　记得当初做这道题的时候，又差分又倍增还开桶，十分毒瘤，后来学到了线段树合并，又看到了这道题，所以就写了这篇解题报告。

　　每一条从S到T的路径（其实就是链），可以拆分为S -> lca -> T，一段深度减少，一段深度增加（或者只有一段，不过性质是一样的）所以我们想一想可以明白，对于每个点，我们可以向其子树中存在的起点和终点统计这个点的观察员会不会碰上这条线路的人。

　　而我们怎么统计呢？

　　我们是否有一种办法，可以把一个点的询问放在线段树上处理，然后就可以理所应当的用线段树合并的手段，来自下而上处理每个点的询问。

　　我们考虑，当我们当前要处理的点在某条路线的S -> lca这一段，那么当前位置设为x，对于所有的S，假如depth[S]=w[x]（即深度等于这个观察员记录的时间）这样的S可以贡献x点的答案。

　　当我们要处理的点在某条路线的lca -> T这一段上，我们需要和刚才那种区别处理，为了不重复统计，或许可以开不同的线段树，但是未免太不优秀了，所以我们用这样的手法。

 

　　首先一个背景是，我们对于每一个点开两个vector，一个代表插入标记，一个代表待删除标记。对于一条路线，我们于起点处打一个插入标记，值为depth[S]，在终点处打一个插入标记，值为2*depth[lca(S,T)] - depth[S]，引用某位大神的思路，这个相当于把起点沿着lca翻上去的这么一个位置。然后这两个标记，当我们统计到lca以上的时候，需要消除这两个位置的贡献，那我们就需要在lca(S,T)和fa[lca(S,T)]两个点打上相应的删除标记来消除贡献，（其实只要递归的时候在相应节点的线段树上，用单点修改把标记一口气都打上，之后我们只要在回溯的时候合并线段树就可以让每个标记按照题意贡献答案，这也是这种思路的巧妙之处）

　　这样分有什么好处？

　　首先好统计，假如在x点，找到的在depth[x] + w[x]处如果有标记，有几个标记就代表有几个起点出发的玩家会被这个观察员看到，然后如果找到depth[x] - w[x]处如果有标记，有几个标记就代表有几个从lca到终点的玩家会被这个节点的观察员看到。

　　其次是贡献不会互相影响，depth[x] + w[x]一定比x点深，于是不可能是被翻上去的那个（大白话很好理解），所以是起点的标记，同理呢，depth[x] - w[x]一定是被翻上去的那个。

　　而且，已经统计过的整条链会在lca处被删除所有贡献，所以答案正确性毫无问题，复杂度是O(NlogN)的，也说的过去。

　　（但是实测，下面这份代码稍微差点的评测机就会TLE，我也不知道为什么）

代码：

#include<bits/stdc++.h>
#define inf 600000
#define lc(x) t[x].l
#define rc(x) t[x].r
using namespace std;
const int N=300005,M=20000005;
struct segt{int l,r,sm;}t[M];
struct node{int y,nxt;}e[N*3];
vector<int>p1[N],p2[N];int h[N],c=1;
int n,m,ans[N],q[N],rt[N],d[N],fa[N][20],cnt;
void add(int x,int y){
    e[++c]=(node){y,h[x]};h[x]=c;
    e[++c]=(node){x,h[y]};h[y]=c;
} int dfs(int x,int f){
    fa[x][0]=f;rt[x]=x;++cnt;
    for(int i=1;i<=19;i++)
    fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=h[x],y;i;i=e[i].nxt)
    if((y=e[i].y)!=f) d[y]=d[x]+1,dfs(y,x);
} int lca(int x,int y){
    if(d[x]<d[y]) swap(x,y);
    for(int i=19;~i;i--)
    if(d[fa[x][i]]>=d[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=19;~i;i--){
        if(fa[x][i]!=fa[y][i])
        x=fa[x][i],y=fa[y][i];
    } return fa[x][0];
} int pushup(int x){
    t[x].sm=t[lc(x)].sm+t[rc(x)].sm;
} int update(int &x,int l,int r,int p,int v){
    if(!x) x=++cnt;if(l==r){
        t[x].sm+=v;return 0;
    } int mid=l+r>>1;
    if(p<=mid) update(lc(x),l,mid,p,v);
    else update(rc(x),mid+1,r,p,v);
    pushup(x);return 0;
} int query(int x,int l,int r,int p){
    if(l==r) return t[x].sm;int mid=l+r>>1;
    if(p<=mid) return query(lc(x),l,mid,p);
    else return query(rc(x),mid+1,r,p);
} int merge(int x,int y,int l,int r){
    if(!x||!y) return x|y;int mid=l+r>>1;
    if(l==r){
        t[x].sm+=t[y].sm;return x;
    } t[x].l=merge(lc(x),lc(y),l,mid);
    t[x].r=merge(rc(x),rc(y),mid+1,r);
    pushup(x);return x;
} int solve(int x,int f){
    for(int i=0;i<p1[x].size();i++)
    update(rt[x],0,inf,p1[x][i],1);
    for(int i=0;i<p2[x].size();i++)
    update(rt[x],0,inf,p2[x][i],-1);
    for(int i=h[x],y;i;i=e[i].nxt)
    if((y=e[i].y)!=f) solve(y,x),
    merge(rt[x],rt[y],0,inf);
    if(d[x]+n-q[x]>=0) ans[x]+=
    query(rt[x],0,inf,d[x]+n-q[x]);
    if(d[x]+n+q[x]<=inf&&q[x]) ans[x]+=
    query(rt[x],0,inf,d[x]+n+q[x]);
} int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;i++)
    scanf("%d%d",&x,&y),add(x,y);
    for(int i=1;i<=n;i++)
    scanf("%d",&q[i]);d[1]=1;dfs(1,0);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);int a=lca(x,y);
        p1[x].push_back(d[x]+n);
        p1[y].push_back(n+2*d[a]-d[x]);
        p2[a].push_back(d[x]+n);
        p2[fa[a][0]].push_back(n+2*d[a]-d[x]);
    } solve(1,0);for(int i=1;i<=n;i++)
    printf("%d ",ans[i]);return 0;
}