转载请注明出处:http://tokitsukaze.live/

题目链接:https://nanti.jisuanke.com/t/31451


题意:
给一棵有根树,根为1。根的深度为0。每个节点初始值为0。
两种操作:
1 L X:把深度为L的节点的值增加X。
2 X:询问X的子树的和。


题解:
做个dfs序,开个树状数组维护。
设定阈值sq=sqrt(n)。
对于深度L:
1.深度为L的节点个数小于等于sq时,我们可以暴力枚举每个节点在树状数组内更新。
2.深度为L的节点个数大于sq时,记录这个深度的修改量,查询的时候,遍历有修改过的深度,二分查询有多少个节点在子树中,乘上这个深度的修改量即可。

这么做均摊了一下复杂度,复杂度是根号级别的。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
#ifdef tokitsukaze
freopen("TEST.txt","r",stdin);
#endif
go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=1e5+10;
const ll mod=1e9+7;
/********************************* head *********************************/
struct Fenwick_Tree
{
#define type ll
type bit[MAX];
int n;
void init(int _n){n=_n;mem(bit,0);}
int lowbit(int x){return x&(-x);}
void insert(int x,type v)
{
while(x<=n)
{
bit[x]+=v;
x+=lowbit(x);
}
}
type get(int x)
{
type res=0;
while(x)
{
res+=bit[x];
x-=lowbit(x);
}
return res;
}
type query(int l,int r)
{
return get(r)-get(l-1);
}
#undef type
}tr;
VI mp[MAX],h[MAX];
ll tag[MAX];
int l[MAX],r[MAX],tot,deep[MAX];
void dfs(int x,int fa,int dep)
{
deep[x]=dep;
l[x]=++tot;
h[dep].pb(l[x]);
for(auto to:mp[x])
{
if(to==fa) continue;
dfs(to,x,dep+1);
}
r[x]=tot;
}
void go()
{
int n,q,i,a,b,op,L;
ll x;
while(read(n,q))
{
for(i=0;i<=n;i++)
{
h[i].clear();
mp[i].clear();
tag[i]=0;
}
for(i=1;i<n;i++)
{
read(a,b);
mp[a].pb(b);
}
tot=0;
dfs(1,0,0);
for(i=0;i<=n;i++) sort(all(h[i]));
tr.init(n);
int sq=sqrt(n+0.5);
set<int> s;
while(q--)
{
read(op);
if(op==1)
{
read(L,x);
if(L>n) continue;
if(sz(h[L])<=sq)
{
for(auto it:h[L])
{
tr.insert(it,x);
}
}
else
{
s.insert(L);
tag[L]+=x;
}
}
else
{
read(x);
ll ans=tr.query(l[x],r[x]);
for(auto it:s)
{
if(it<deep[x]) continue;
int tl,tr;
tr=upper_bound(all(h[it]),r[x])-h[it].begin();
tl=lower_bound(all(h[it]),l[x])-h[it].begin();
ans+=tag[it]*(tr-tl);
}
printf("%lld\n",ans);
}
}
}
}