P1600 【天天爱跑步】

· · 题解

纪念一下noip神题

结合代码读文章是好习惯 。

题目

好像简述和没简述差不多 。 所以偷工减料一下 。

分析

首先，观察部分分 。我们发现它有测试点只上行或者之下行 。

由此我们得到启发 ，我们将一段运动拆分为上行和下行两个部分 。

显然他们的中转点是他们的最近公共祖先 。

但要注意不要多次处理公共祖先 。本文采用如下拆分（丑陋勿喷 ）：

提供代码：

LCA:

void lca1(int a,int f){
    fa[a][0]=f;
    dep[a]=dep[f]+1;
    for(int i=1;i<=20;++i){
        fa[a][i]=fa[fa[a][i-1]][i-1];
    }
    for(int i=ves[a];i;i=st[i].next){
        if(st[i].v!=f)lca1(st[i].v,a);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[fa[x][i]]<dep[y])continue;
        x=fa[x][i];
    }
    if(x==y)return y;
    for(int i=20;i>=0;i--){
        if(fa[x][i]==fa[y][i])continue;
        x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}

拆分程序：

for(int i=1;i<=m;++i){//add操作后面解释
        int a,b,c;
        scanf("%d%d",&a,&b);
        c=lca(a,b);int d=a;
        add(c,dep[c]*2-dep[a],1);//添加链表
        add(b,dep[c]*2-dep[a],2);//此为下行
        if(c==a)continue;//不存在上行
        for(int i=20;i>=0;i--){
            if(dep[fa[d][i]]<=dep[c])continue;
            d=fa[d][i];
        }//倍增法求顶部结点 。
        add(d,dep[a],1);
        add(a,dep[a],2);//上行添加
    }

对于上行来说，其开始点便是其中一个端点 ,即代码中的 a ，贡献的层数便是 a 的层数 。 对于下行来说 ， 其贡献的层数相当于 dep[c]-(dep[a]-dep[c]) （这个值可能会爆负数用 y 数组维护一下）可以理解为将 a 点往上翻后所在的层数 。

为了防止结点重复被分到上行和下行中 ，使用点 d 表是第一段的结束点 。 显然 d 为 c 的儿子节点（最近的那个），且为 a 的祖先 （可能会比较远）。

在 c=a 时则没有上行段。

如何添加路径信息呢？

为了后期dfs的查找 ，我们使用链表结构 ，类似链式前向心的方法 。 在递归到该节点时，我们就可以直接查找 。

void add(int a,int b,int type){//信息什么用后面解释。
    k++;
    w[k].u=a;//该节点
    w[k].type=type;//类型位于上方的结点为1，下方的为2.
    w[k].dep=b;//对第几层有贡献，可能会有负数
    w[k].next=vesv[a];//链表操作
    vesv[a]=k;
}

接下来就剩下 dfs 遍历树了。

首先，如果该点的观察员第 k 秒出现 ，那么它观察到的人一定会从离他 k 远的结点跑来 。于是我们用 x 数组表示整数贡献 ，y 表示负数贡献 （可能会出现,在下行时）。

由于不好直接在路径上统计 ，所以使用差分对其维护。 给张图吧

大致是这样的 。

先求大范围，如何删去多余的部分 。

具体点是什么呢 ，对于每个结点来说 ，其答案要不然从上往下走 （即从 dep[a]-see[a] 往下走），要么从下往上走（即 dep[a]-see[a] 往上走）。答案直接从之前贡献的值中提取 。

画个图模拟一下 ，我们发现如果在递归子节点前提取答案 我们更新的结点是大范围的 ，而在递归子节点后 我们更新的节点是小范围的 。

哦吼！把这两个一相减不就是我们要的答案了吗 。妙！

看代码比较形象 ：

void dfs(int a){
    for(int i=vesv[a];i;i=w[i].next){
        if(w[i].type==1){
            if(w[i].dep>=0)x[w[i].dep]++;//贡献增加
            else y[-w[i].dep]++;}//负数处理
    }
    if(see[a]==0)ans[a]+=x[dep[a]];//为0特殊传递，否则会翻倍 。
    else{//此步求大范围
        ans[a]+=x[dep[a]+see[a]];
        if(dep[a]-see[a]>=0)//判断是否特殊处理
           ans[a]+=x[dep[a]-see[a]];
        else ans[a]+=y[see[a]-dep[a]];
    }
    for(int i=ves[a];i;i=st[i].next)
        if(st[i].v!=fa[a][0])dfs(st[i].v);
    for(int i=vesv[a];i;i=w[i].next){
        if(w[i].type==2){   //贡献结束，不对后面的数再有贡献
            if(w[i].dep>=0)x[w[i].dep]--;
            else y[-w[i].dep]--;
        }
    }
    if(see[a]==0)ans[a]-=x[dep[a]];
    else{//删去多余部分
        if(dep[a]-see[a]>=0)ans[a]-=x[dep[a]-see[a]];
        else ans[a]-=y[see[a]-dep[a]];
        ans[a]-=x[dep[a]+see[a]];
    }
}

完整代码

100行代码 ，时间复杂度O(n\log n+n+m) 如果水平可以的话 (LCA+答案统计+贡献增加) 【忽略常数】

解释均在上文呈现。

（只是为了完整性）

#include<bits/stdc++.h>
using namespace std;
const int maxn=600009;
struct ss{
    int u,v,next;
}st[maxn*4];
int k,ves[maxn],fa[maxn][25],see[maxn],dep[maxn],vesv[maxn],x[maxn*4],y[maxn*4],ans[maxn];
void cc(int a,int b){//建边 
    k++;
    st[k].u=a;
    st[k].v=b;
    st[k].next=ves[a];
    ves[a]=k;
}
struct way{
    int u,dep,next,type;
}w[maxn*4];
void add(int a,int b,int type){//信息什么用后面解释。
    k++;
    w[k].u=a;//该节点
    w[k].type=type;//类型位于上方的结点为1，下方的为2.
    w[k].dep=b;//对第几层有贡献
    w[k].next=vesv[a];//链表操作
    vesv[a]=k;
}
void lca1(int a,int f){//LCA自行查看模板 
    fa[a][0]=f;
    dep[a]=dep[f]+1;
    for(int i=1;i<=20;++i){
        fa[a][i]=fa[fa[a][i-1]][i-1];
    }
    for(int i=ves[a];i;i=st[i].next){
        if(st[i].v!=f)lca1(st[i].v,a);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[fa[x][i]]<dep[y])continue;
        x=fa[x][i];
    }
    if(x==y)return y;
    for(int i=20;i>=0;i--){
        if(fa[x][i]==fa[y][i])continue;
        x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}
void dfs(int a){
    for(int i=vesv[a];i;i=w[i].next){
        if(w[i].type==1){
            if(w[i].dep>=0)x[w[i].dep]++;//贡献增加
            else y[-w[i].dep]++;}//负数处理
    }
    if(see[a]==0)ans[a]+=x[dep[a]];//为0特殊传递，否则会翻倍 。
    else{//此步求大范围
        ans[a]+=x[dep[a]+see[a]];
        if(dep[a]-see[a]>=0)//判断是否特殊处理
           ans[a]+=x[dep[a]-see[a]];
        else ans[a]+=y[see[a]-dep[a]];
    }
    for(int i=ves[a];i;i=st[i].next)
        if(st[i].v!=fa[a][0])dfs(st[i].v);
    for(int i=vesv[a];i;i=w[i].next){
        if(w[i].type==2){   //贡献结束，不对后面的数再有贡献
            if(w[i].dep>=0)x[w[i].dep]--;
            else y[-w[i].dep]--;
        }
    }
    if(see[a]==0)ans[a]-=x[dep[a]];
    else{//删去多余部分
        if(dep[a]-see[a]>=0)ans[a]-=x[dep[a]-see[a]];
        else ans[a]-=y[see[a]-dep[a]];
        ans[a]-=x[dep[a]+see[a]];
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        cc(a,b);
        cc(b,a);
    }
    dep[1]=1;k=0;
    lca1(1,0);
    for(int i=1;i<=n;++i)scanf("%d",&see[i]);//观察时间 
    for(int i=1;i<=m;++i){
        int a,b,c;
        scanf("%d%d",&a,&b);
        c=lca(a,b);int d=a;
        add(c,dep[c]*2-dep[a],1);//添加链表
        add(b,dep[c]*2-dep[a],2);//此为下行
        if(c==a)continue;//不存在上行
        for(int i=20;i>=0;i--){
            if(dep[fa[d][i]]<=dep[c])continue;
            d=fa[d][i];
        }//倍增法求顶部结点 。
        add(d,dep[a],1);
        add(a,dep[a],2);//上行添加
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);//输出 
    } 
    return 0;
}

感谢阅读 ，欢迎纠错 （评论点赞）。