1 条题解

  • -1
    @ 2019-06-06 15:57:46

    将每个玩家的路径拆分出来考虑。具体地说,对于玩家i,从\(S_{i}\)到\(T_{i}\)的路径拆分为\(S_{i}\)到\(lca(S_{i},T_{i})\)和\(lca(S_{i},T_{i})\)到\(T_{i}\)。
    首先考虑从\(S_{i}\)到\(lca(S_{i},T_{i})\)的路径。
    若这条路径上的点x能够观察到玩家i。那么等价于\(d\left [ S_{i} \right ]-d\left [ x \right ]=W\left [ x \right ]\)将其变形得\(d\left [ S_{i} \right ]=d\left [ x \right ]+W\left [ x \right ]\)。(\(d\left [ i \right ]\)表示i结点在树上的深度)这个式子可以抽象为在\(S_{i}\)到\(lca(S_{i},T_{i})\)的路径上的所有点都增加了一个类型为\(d\left [ x \right ]+W\left [ x \right ]\)的物品。最终这个点x的观察员能够观察到的人数就是这个点的类型为\(d\left [ x \right ]+W\left [ x \right ]\)物品数的和。另一条链的关系可以类似得到。
    具体到实现中,有如下几点需要注意。
    1 为了高效的对一条路径上的点修改,可以在树上对点差分,配合LCA的倍增算法可以实现O(nlogn)的复杂度。
    2 本题最后对物品数求和的过程是动态开点的权值线段树的裸题。但是在这道题目中直接使用权值线段树会爆空间。仔细观察所求的值,会发现这个值具有区间可加性,意味着可以在dfs进入某棵子树时维护两个变量val1和val2分别代表两段上的答案,在对整棵子树结束访问时重新计算val1和val2的差值,就是这棵子树对答案的贡献。在代码中,用了c数组进行计数。
    3 玩家i路径上的另一段,也就是\(lca(S_{i},T_{i})\)到\(T_{i}\)的部分可能会出现c数组下标为负数的情况,所以这里要进行数组下标平移或者离散化,这里代码中用的是数组下标平移的方式。
    代码如下

    /*
    
    */
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<vector>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    typedef long long ll;
    typedef pair<int,int>pii;
    const int maxn=300000+5;
    const int INF=0x3f3f3f3f;
    int n,m;
    struct node {
        int from,to;
    } edge[maxn*2];
    int t,head[maxn],tot=0,ans[maxn],fa[maxn][20],d[maxn],v[maxn],c1[maxn*2],c2[maxn*2],w[maxn];
    vector<int>a1[maxn],a2[maxn],b1[maxn],b2[maxn];
    void add(int u,int v) {
        edge[++tot].to=v;
        edge[tot].from=head[u];
        head[u]=tot;
    }
    void bfs() {
        queue<int>q;
        q.push(1);
        d[1]=1;
        while(!q.empty()) {
            int x=q.front();
            q.pop();
            for(int i=head[x]; i!=-1; i=edge[i].from) {
                int y=edge[i].to;
                if(!d[y]) {
                    q.push(y);
                    d[y]=d[x]+1;
                    fa[y][0]=x;
                    for(int j=1; j<=t; j++) {
                        fa[y][j]=fa[fa[y][j-1]][j-1];
                    }
                }
            }
        }
    }
    int lca(int x,int y) {
        if(d[x]>d[y]) swap(x,y);
        for(int i=t; i>=0; i--) {
            if(d[fa[y][i]]>=d[x]) {
                y=fa[y][i];
            }
        }
        if(x==y) return x;
        for(int i=t; i>=0; i--) {
            if(fa[x][i]!=fa[y][i]) {
                x=fa[x][i];
                y=fa[y][i];
            }
        }
        return fa[x][0];
    }
    void dfs(int x) {
        v[x]=1;
        int val1=c1[w[x]+d[x]],val2=c2[w[x]-d[x]+n];
        for(int i=head[x]; i!=-1; i=edge[i].from) {
            int y=edge[i].to;
            if(!v[y]) {
                dfs(y);
            }
        }
        for(int i=0;i<a1[x].size();i++) c1[a1[x][i]]++;
        for(int i=0;i<b1[x].size();i++) c1[b1[x][i]]--;
        for(int i=0;i<a2[x].size();i++) c2[a2[x][i]+n]++;
        for(int i=0;i<b2[x].size();i++) c2[b2[x][i]+n]--;
        ans[x]+=c1[d[x]+w[x]]-val1+c2[w[x]-d[x]+n]-val2;
    }
    int main() {
        ios::sync_with_stdio(false);
        //freopen("天天爱跑步.in","r",stdin);
        memset(head,-1,sizeof(head));
        cin>>n>>m;
        t=(int)(log(n)/log(2))+1;
        int u,v;
        for(int i=1; i<=n-1; i++) {
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        bfs();
        int x,y;
        for(int i=1;i<=n;i++) cin>>w[i];
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            int z=lca(x,y);
            a1[x].push_back(d[x]);
            b1[fa[z][0]].push_back(d[x]);
            a2[y].push_back(d[x]-2*d[z]);
            b2[z].push_back(d[x]-2*d[z]);
        } 
        dfs(1);
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<" ";
        }
        return 0;
    }
    
  • 1

信息

ID
1077
难度
2
分类
(无)
标签
递交数
25
已通过
20
通过率
80%
上传者