NOIP2016(D1T2)天天爱跑步——用桶存储贡献，dfn差分

· · 个人记录

暴力25pts

对于每个玩家，考虑求 LCA 暴力遍历树上路径的每一个点

如果对于节点P，玩家恰好在 w_P 时刻到达，那么观察到的玩家数+1

时间复杂度 O(mn)

Code:

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e4+5;

int fa[MAXN],siz[MAXN],dep[MAXN],hson[MAXN];
vector<int > edge[MAXN];

int w[MAXN];

int n,m;

void dfs(int x){
    siz[x]=1;
    dep[x]=dep[fa[x]]+1;
    for(auto v:edge[x]){
        if(v==fa[x]) continue;
        fa[v]=x;
        dfs(v);
        siz[x]+=siz[v];
        if(!hson[x] || siz[hson[x]]<=siz[v]) hson[x]=v;
    }
}//

int top[MAXN],ans[MAXN];

void dfs2(int x,int h){
    top[x]=h;
    if(hson[x]) dfs2(hson[x],h);
    for(auto v:edge[x]){
        if(v==fa[x]) continue;
        if(v==hson[x]) continue;
        dfs2(v,v);
    }
}//

int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) swap(x,y);
    return y;
}//

void stats(int s,int t,int lca){
    int cnt=0;
    while(s!=lca){
        if(w[s]==cnt) ++ans[s];
        s=fa[s];
        ++cnt;
    }
    if(w[s]==cnt) ++ans[s];
    cnt+=dep[t]-dep[lca];
    while(t!=lca){
        if(w[t]==cnt) ++ans[t];
        t=fa[t];
        --cnt;
    }
}// 

void work(){
    int x,y,lca;

    scanf("%d%d",&n,&m);

    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    for(int i=1;i<=n;++i){
        scanf("%d",&w[i]);
    }

    dfs(1);
    dfs2(1,1);

    while(m--){
        scanf("%d%d",&x,&y);
        lca=LCA(x,y);
        stats(x,y,lca);
    }

    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
}

int main(){
    work();
    return 0;
}

正解

我们发现如果以每个玩家来考虑对每个点的贡献，时间复杂度无法突破

如果要进行突破的话，肯定是需要进行标记后一次遍历直接求出答案

考虑对于一个点 P ，它是否被路径 <u,v> 贡献

首先， P 必然在 <u,v> 上，也就是说， \{u,v\} 中必然有一个点在以P为根的子树里

其次，有两种情况，要分类讨论

上行路段

即<u,LCA_{u,v}>这段路径上

此时若能对P产生贡献，必然满足

w_P=dep_u-dep_P

移项得

dep_s=dep_P+w_P

可以发现，等式的左右边各自只与一个节点有关

下行路段

即<LCA_{u,v},v>这段路径上

此时若能对P产生贡献，寻找等量关系得到

w_P+dep_v-dep_P=dis_{u,v} _{(其中dis_{u,v}为<u,v>路径的长度)}

移项得

dis_{u,v}-dep_v=dep_P-w_P

又出现了，等式的左右边各自只与一个节点有关(路径长可以预处理)

用桶统计

发现无论是上行路段还是下行路段，所需要的条件都可以转化为一个左右边各自只与一个点有关的等式

那么，路径可以单独处理，用两个桶分别储存上行和下行的点

即对于b1_i，储存目前遇到的dep=i的节点数；同时对于b2_i,储存目前遇到的dis-dep=i的节点数

为什么要说目前遇到的呢，这是因为有些时候储存的这个点并不在子树中，具体看代码

这样的话时间复杂度就为O(m \log n),可以通过

关于实现还有一些细节，具体看代码

AC Code:

#include <bits/stdc++.h>

using namespace std;

const int MAXN=3e5+5;

int dep[MAXN],siz[MAXN],fa[MAXN],hson[MAXN];
vector<int > edge[MAXN];
int w[MAXN];

void dfs1(int x){
    dep[x]=dep[fa[x]]+1;
    siz[x]=1;
    for(auto v:edge[x]){
        if(v==fa[x]) continue;
        fa[v]=x; 
        dfs1(v);
        siz[x]+=siz[v];
        if(!hson[x] || siz[hson[x]]<siz[v]) hson[x]=v;
    }
}//

int top[MAXN];

void dfs2(int x,int h){
    top[x]=h;
    if(hson[x]) dfs2(hson[x],h);
    for(auto v:edge[x]){
        if(v==fa[x]) continue;
        if(v==hson[x]) continue;
        dfs2(v,v);
    }
}//

int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) swap(x,y);
    return y;
}//

//以上为树剖求LCA模板

int b1[MAXN<<1],b2[MAXN<<1];//第一个存产生贡献的起点，第二个存产生贡献的终点
int dis[MAXN];//每条路径的路径长
int s[MAXN],t[MAXN];//每条路径的起点和终点 
int bgn[MAXN];//以这个节点为起点的路径条数
int ans[MAXN];
vector<int > ed[MAXN],lca[MAXN]; //以这个节点为终点/LCA的路径集合 

void dfs(int x){
    int t1=b1[dep[x]+w[x]],t2=b2[MAXN+w[x]-dep[x]];
//这里需要记录之前的值，因为dfs到这个点了，说明以它为根的子树所造成的贡献都没有被统计
//而能对这个结点产生贡献的只有这个子树中的节点，所以对它造成贡献的点就只有这次dfs后增加的数值
//要进行一个容斥 
//此外，w[x]-dep[x]有可能为负，此处均向右平移MAXN个单位长度 
    for(auto v:edge[x]){
        if(v==fa[x]) continue;
        dfs(v);
    }

    b1[dep[x]]+=bgn[x];//统计起点
    for(auto v:ed[x]) b2[MAXN+dis[v]-dep[t[v]]]++;//统计终点 

    ans[x]+=b1[dep[x]+w[x]]+b2[MAXN+w[x]-dep[x]]-t1-t2;//统计这次dfs做出的贡献

    for(auto v:lca[x]){//路径在lca之上就结束了,不会再产生贡献 
        b1[dep[s[v]]]--;
        b2[MAXN+dis[v]-dep[t[v]]]--;
    } 
}//

int n,m;

void work(){
    int u,v,l;

    scanf("%d%d",&n,&m);
    for(int i=1;i<n ;++i){
        scanf("%d%d",&u,&v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    dfs1(1);
    dfs2(1,1);

    for(int i=1;i<=n;++i) scanf("%d",&w[i]);

    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        bgn[u]++;
        ed[v].push_back(i);
        l=LCA(u,v);
//      printf("%d\n",l);
        lca[l].push_back(i);
        dis[i]=dep[u]+dep[v]-dep[l]*2;
        s[i]=u,t[i]=v;
        if(dep[u]==dep[l]+w[l]) ans[l]--;//lca如果可以被贡献到，则会被贡献两次 
    }

    dfs(1);

    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
}//

int main(){
    work();
    return 0;
}

附记

对使用桶的思考

这次可以使用桶是因为条件等式可以被转化成两端各自只与一个节点有关的式子

也就是说，对于一个可能做出贡献的路径，它在桶中的位置是不会随着查询它的点的变化而变化的

这大概就是使用桶的条件之一？