1 条题解

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

    *【树上点差分】树结构点修改、区间查询[LOJ144]DFS序1

    信息

    ID
    110
    时间
    2000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    125
    已通过
    37
    上传者