1 条题解

  • 0
    @ 2025-10-8 16:51:25
    #include<bits/stdc++.h>
    #define LL long long
    #define eb emplace_back
    using namespace std;
    const int N=1e6+10;
    vector<int>G[N];
    LL v[N],a[N],d[N];
    int dfn[N],siz[N],tsp,n,m,rt;;
    void dfs(int x,int xfa)
    {
    	dfn[x]=++tsp;siz[x]=1;
    	for(int y:G[x])if(y!=xfa)
    	{
    		dfs(y,x);
    		siz[x]+=siz[y];
    	}
    }
    LL c1[N],c2[N];
    void add(LL c[],int x,LL k){for(;x<=n;x+=x&-x)c[x]+=k;}
    LL sum(LL c[],int x){LL res=0;for(;x>=1;x-=x&-x)res+=c[x]; return res;}
    LL getsum(int x){ return sum(c1,x)*x-sum(c2,x); }
    int main()
    {
        scanf("%d%d%d",&n,&m,&rt);
        for(int i=1;i<=n;i++)scanf("%lld",&v[i]);
        for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),G[x].eb(y),G[y].eb(x);
    
        tsp=0;dfs(rt,0);
        a[0]=0;for(int i=1;i<=n;i++)a[dfn[i]]=v[i];
    
        memset(c1,0,sizeof(c1));memset(c2,0,sizeof(c2));
        for(int i=1;i<=n;i++)
    	{
    		d[i]=a[i]-a[i-1];
    		add(c1,i,d[i]),
    		add(c2,i,d[i]*(i-1));
    	}
    
        for(int i=1;i<=m;++i)
        {
        	int op;scanf("%d",&op);
        	if(op==1)//1 x k,表示将结点 x 的子树上所有结点的权值增加 k
        	{
        		int p;LL k;scanf("%d%lld",&p,&k);
        		int l=dfn[p],r=dfn[p]+siz[p]-1;
    
        		add(c1,l,k);
                add(c1,r+1,-k);
    
        		add(c2,  l   ,  k*(l-1) );
        		add(c2,  r+1,   -k*r    );
        	}
        	else//2 x,表示求结点 x 的子树上所有结点的权值之和
        	{
        		int x;scanf("%d",&x);
        		int l=dfn[x],r=dfn[x]+siz[x]-1;
        		printf("%lld\n", getsum(r) - getsum(l-1) );
        	}
        }
        return 0;
    }
    
    • 1

    *【树上点差分】树结构区间修改、区间求和[LOJ145]DFS序2

    信息

    ID
    118
    时间
    2000ms
    内存
    128MiB
    难度
    9
    标签
    递交数
    196
    已通过
    20
    上传者