BZOJ 4034 BIT & Dfs序

调了恒久突然发现输出优化忘记带负号了..
就是差分树状数组维护Dfs序即可。
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #define LL long long
 6 using namespace std;
 7 
 8 inline void Get_Int(LL &x)
 9 {
10     x=0;  char ch=getchar(); LL f=1;
11     while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
12     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} x*=f;
13 }
14 inline void Put_Int(LL x)
15 {
16     char ch[30]; LL top=0;
17     if (x<0) putchar('-'),x=-x;
18     if (x==0) ch[++top]='0';
19     while (x) ch[++top]=x%10+'0',x/=10;
20     while (top) putchar(ch[top--]); putchar('
');
21 }
22 //=============================================
23 const LL Maxn=100100;
24 LL Begin[Maxn],End[Maxn],c[Maxn],cv[Maxn],a[Maxn];
25 LL head[Maxn],dep[Maxn];
26 bool vis[Maxn];
27 LL u,v,w,n,m,Type,cnt,tot;
28 struct Edge{LL to,next;}edge[Maxn<<2];
29 inline LL lowbit(LL x) {return x&(-x);}
30 struct BIT
31 {
32     LL c[Maxn];
33     inline void Add(LL x,LL v) {for (LL i=x;i<=n;i+=lowbit(i)) c[i]+=v;}
34     inline LL Sum(LL x) {LL ret=0; for (LL i=x;i;i-=lowbit(i)) ret+=c[i]; return ret;}
35     inline void Interval(LL x,LL y,LL w) {Add(x,w),Add(y+1,-w);}
36 }Bit1,Bit2;
37 inline void AddE(LL u,LL v) 
38 {edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}
39 
40 void Dfs(LL u) 
41 {
42     Begin[u]=++tot; vis[u]=true;
43     for (LL i=head[u];i!=-1;i=edge[i].next)
44         if (!vis[edge[i].to]) 
45             dep[edge[i].to]=dep[u]+1,Dfs(edge[i].to);
46     End[u]=tot;
47 }
48 
49 inline void Modify_Point()
50 {Get_Int(u),Get_Int(w);Bit1.Interval(Begin[u],End[u],w);}
51 inline void Modify_Tree()
52 {Get_Int(u),Get_Int(w);Bit1.Interval(Begin[u],End[u],(1-dep[u])*w);Bit2.Interval(Begin[u],End[u],w);}
53 inline LL Query()
54 {Get_Int(u);return Bit1.Sum(Begin[u])+Bit2.Sum(Begin[u])*dep[u];}
55 
56 int main()
57 {
58     Get_Int(n),Get_Int(m);
59     for (LL i=1;i<=n;i++) Get_Int(a[i]);
60     memset(head,-1,sizeof(head)); tot=0;
61     for (LL i=1;i<n;i++) 
62         Get_Int(u),Get_Int(v),AddE(u,v),AddE(v,u);
63     memset(vis,false,sizeof(vis)); Dfs(1);
64     for (LL i=1;i<=n;i++) Bit1.Interval(Begin[i],End[i],a[i]);
65     for (LL i=1;i<=m;i++)
66     {
67         Get_Int(Type);
68         if (Type==1) Modify_Point();
69         if (Type==2) Modify_Tree();
70         if (Type==3) Put_Int(Query());
71     }
72     return 0;
73 }
C++