题解：AT_abc187_e [ABC187E] Through Path

Hog_Dawa_IOI · 2023-10-12 20:21:04 · 题解

题目大意不用多讲，大家都懂。
这是根据样例一画的图。

首先，为了方便后面处理，我们使用节点一为根，利用树链剖分，求出每个点的深度以及整棵树的 DFS 序列。
因为一棵子树在 DFS 序列中是一连串的，所以一棵子树可以看做一个连续的区间；而区间修改单点查询，可使用差分数组维护。 接着我们判断我们的方向是由下往上还是由上往下。
这里的方向不是我们通常说的方向，举个例子，样例一中 1 1 1 的意思是从节点 1 出发，不能经过节点 2，而从节点 1 到 节点 2 是往下的，我们就说这个方向是由上往下。

• 如果是由上往下，那么我们把整棵树每个点的权值都加 k，再把以那个不能走的点为根的子树每个点的权值减去 k。
  如同这个 1 1 1 的例子，我们把一整棵树每个点的权值加 1，再把以节点 2 为根的子树每个点的权值减去 1。
• 如果是由下往上，那么我们把以起点为根的子树每个点的权值加上 k。
  如同 2 1 100 的例子，我们从 2 出发，不能经过 1，那么我们只需要把以节点 2 为根的子树每个点的权值加上 100 即可。

最后询问的时候就把差分数组的前缀求出来，便可得到原数组。

#include<stdio.h>
#include<string.h>
long long n,q,first[200005],num,numm,a,b,c,x[200005],y[200005];
long long size[200005],father[200005],son[200005],top[200005],duiying[200005],cf[200005];
struct sss{long long end,next;}bian[400005];
void dfs1(long long where,long long fa)
{
    for(int i=first[where];i;i=bian[i].next) if(bian[i].end!=fa)
    {
        father[bian[i].end]=where,dfs1(bian[i].end,where),size[where]+=size[bian[i].end];
        if(size[son[where]]<size[bian[i].end]) son[where]=bian[i].end;
    }
    size[where]++;
}
void dfs2(long long where,long long tops)
{
    top[where]=tops,duiying[where]=++numm;
    if(!son[where]) return;
    dfs2(son[where],tops);
    for(int i=first[where];i;i=bian[i].next) if(bian[i].end!=son[where]&&bian[i].end!=father[where])
    dfs2(bian[i].end,bian[i].end);
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<n;i++) scanf("%lld%lld",&a,&b),x[i]=a,y[i]=b,
    bian[++num].end=b,bian[num].next=first[a],first[a]=num,
    bian[++num].end=a,bian[num].next=first[b],first[b]=num;
    dfs1(1,0),dfs2(1,1);
    scanf("%lld",&q);
    while(q--)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        long long num1,num2;
        if(a==1)
        {
            num1=duiying[x[b]],num2=duiying[y[b]];
            if(num1<num2) cf[1]+=c,cf[n+1]-=c,cf[duiying[y[b]]]-=c,cf[duiying[y[b]]+size[y[b]]]+=c;
            else cf[duiying[x[b]]]+=c,cf[duiying[x[b]]+size[x[b]]]-=c;
        }
        else
        {
            num1=duiying[y[b]],num2=duiying[x[b]];
            if(num1<num2) cf[1]+=c,cf[n+1]-=c,cf[duiying[x[b]]]-=c,cf[duiying[x[b]]+size[x[b]]]+=c;
            else cf[duiying[y[b]]]+=c,cf[duiying[y[b]]+size[y[b]]]-=c;
        }
    }
    for(int i=1;i<=n;i++) cf[i]+=cf[i-1];
    for(int i=1;i<=n;i++) printf("%lld\n",cf[duiying[i]]);
}