洛谷 P3178 [HAOI2015]树上操作

https://www.cnblogs.com/gengchen/p/6530864.html

对于操作1，对于节点x的任意后代节点y，那么可以贡献a

对于操作2，对于节点x的任意后代节点y，那么可以贡献a*(dep[y]−dep[x]+1)

使用两个树状数组来维护贡献（贡献指某点到根的点权和）

其实到这里已经非常明显了啊...为什么我还是看不懂啊

更确切地说，使用两个支持区间修改、单点查询的数据结构x1,x2，用x1[i]、x2[i]分别表示在x1、x2中单点查询位置i的结果，使得最终答案（i点到根的点权和）是x1[i]*dep[i]+x2[i]。

那么，处理出树的dfs序以及各点入栈、出栈时间戳（分别为ll[i],rr[i]）之后，

对于原序列位置i的值aa[i]，相当于在x2中[ll[i],rr[i]]区间加aa[i]

对于操作1，就是在x2中[ll[i],rr[i]]区间加a。

对于操作2，a*(dep[y]-dep[x]+1)=dep[y]*a+a*(-dep[x]+1)，因此相当于在x2中[ll[i],rr[i]]区间加a*(-dep[x]+1)，再在x1中[ll[i],rr[i]]区间加a。

对于操作3，直接查询上述式子的结果即可

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 typedef long long LL;
 5 
 6 template<class T>
 7 inline void read(T &x) {
 8     int f=1;x=0;char ch=getchar();
 9     while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
10     while(ch>='0'&&ch<='9'){x*=10;x+=(ch-'0');ch=getchar();}
11     x*=f;
12 }
13 template<class T>
14 inline void write(T x) {
15     if(x<0) putchar('-'),x=-x;
16     if(x>9) write(x/10);
17     putchar(x%10+'0');
18 }
19 struct E
20 {
21     int to,nxt;
22 }e[200100];
23 int f1[100100],ne;
24 int dep[100100],ll[100100],rr[100100],dfc;
25 int n,m;
26 int aa[100100];
27 struct BIT
28 {
29 #define lowbit(x) ((x)&(-x))
30     LL dat[100100];
31     void _add(int pos,LL num)
32     {
33         while(pos<=n)    dat[pos]+=num,pos+=lowbit(pos);
34     }
35     LL sum(int pos)
36     {
37         LL ans=0;
38         while(pos)    ans+=dat[pos],pos-=lowbit(pos);
39         return ans;
40     }
41     void add(int l,int r,LL x)
42     {
43         _add(l,x);_add(r+1,-x);
44     }
45 #undef lowbit
46 }x1,x2;
47 //实际到根的点权和为x1[i]*dep[i]+x2[i]
48 
49 void dfs(int u,int fa)
50 {
51     ll[u]=++dfc;
52     for(int k=f1[u];k;k=e[k].nxt)
53         if(e[k].to!=fa)
54         {
55             dep[e[k].to]=dep[u]+1;
56             dfs(e[k].to,u);
57         }
58     rr[u]=dfc;
59 }
60 int main()
61 {
62     int i,u,v,idx,x;LL a;
63     read(n);read(m);
64     for(i=1;i<=n;i++)    read(aa[i]);
65     for(i=1;i<n;i++)
66     {
67         read(u);read(v);
68         e[++ne].to=v;e[ne].nxt=f1[u];f1[u]=ne;
69         e[++ne].to=u;e[ne].nxt=f1[v];f1[v]=ne;
70     }
71     dfs(1,0);
72     for(i=1;i<=n;i++)    x2.add(ll[i],rr[i],aa[i]);
73     for(i=1;i<=m;i++)
74     {
75         read(idx);read(x);
76         if(idx==1)
77         {
78             read(a);
79             x2.add(ll[x],rr[x],a);
80         }
81         else if(idx==2)
82         {
83             read(a);
84             x1.add(ll[x],rr[x],a);
85             x2.add(ll[x],rr[x],a*(-dep[x]+1));
86         }
87         else if(idx==3)
88         {
89             write(x1.sum(ll[x])*dep[x]+x2.sum(ll[x]));puts("");
90         }
91     }
92     return 0;
93 }