题目大意
给出一棵树，每次在树上增加/减少权值，维护其带权重心。
题目分析
又没有询问，直接 return 0，假装自己维护了带权重心。
动态点分治入门题。
动态点分治，又称点分树，将树的重心依次连接形成的树，其高度不超过$\log n$。
首先考虑一种暴力的方法。
若存在边$x\rightarrow y$，所有点到$x$的权值和比到$y$的权值和大，即可将带权重心从$x$移动到$y$，这样一定使答案变优。
每次修改不断迭代移动，时间复杂度为$O(n)$。
不妨使用点分树优化暴力。
能够使用点分树的原因：每次可以移动到任意位置，且点分树深度只有$log n$，每个点度数不超过$20$。
因此我们需要计算所有点到一个点的权值和。
我们可以使用点分树保存子树中的权值和。
通过每个点到根路径上权值和的累加可以计算出所有权值和。
显然这样会算重，简单容斥一下，减去每个点到其父亲的权值和，用点分树维护这两个量即可。
代码
预处理log()快得飞起。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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
struct Edge {
int from,to,dist,root;
};
int n,m,root,Min=INT_MAX,Root,step=0,Log[maxn*2],Dfn[maxn],f[maxn*2][25],Size[maxn],father[maxn];
bool vst[maxn];
LL Dist[maxn],val1[maxn],val2[maxn],num[maxn];
vector<Edge>edges[maxn];
void AddEdge(int x,int y,int v) {
edges[x].push_back((Edge) {x,y,v});
}
void Dfs(int Now,int fa,LL dist) {
Dfn[Now]=++step;
Dist[Now]=f[step][0]=dist;
for(Edge& e:edges[Now]) {
int Next=e.to;
if(Next==fa)continue;
Dfs(Next,Now,dist+e.dist);
f[++step][0]=dist;
}
}
int RMQ(int Left,int Right) {
if(Right<Left)swap(Left,Right);
int x=Log[Right-Left+1];
return min(f[Left][x],f[Right-(1<<x)+1][x]);
}
LL dist(int x,int y) {
return Dist[x]+Dist[y]-2*RMQ(Dfn[x],Dfn[y]);
}
void Sparse_Table() {
for(int j=1; (1<<j)<=step; j++)
for(int i=1; i+(1<<j)-1<=step; i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
void Get_Root(int Now,int fa,int all) {
Size[Now]=1;
int Max=0;
for(Edge& e:edges[Now]) {
int Next=e.to;
if(Next==fa||vst[Next])continue;
Get_Root(Next,Now,all);
Size[Now]+=Size[Next];
Max=max(Max,Size[Next]);
}
Max=max(Max,all-Size[Now]);
if(Max<Min) {
Min=Max;
root=Now;
}
}
void build(int Now) {
vst[Now]=1;
for(Edge& e:edges[Now]) {
int Next=e.to;
if(vst[Next])continue;
Min=INT_MAX;
Get_Root(Next,0,Size[Next]);
father[root]=Now;
e.root=root;
build(root);
}
}
LL Cal(int x) {
LL ans=0;
for(int i=x; i; i=father[i])ans+=val1[i]+num[i]*dist(x,i);
for(int i=x; father[i]; i=father[i])ans-=val2[i]+num[i]*dist(x,father[i]);
return ans;
}
LL Query() {
int Now=Root,Go;
LL Min;
while(true) {
Min=Cal(Now);
Go=Now;
for(Edge& e:edges[Now]) {
if(!e.root)continue;
int Next=e.to;
LL val=Cal(Next); //!!!
if(val<Min) {
Min=val;
Go=e.root;
}
}
if(Go==Now)break;
Now=Go;
}
return Min;
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y,v);
AddEdge(y,x,v);
}
Dfs(1,0,0);
Sparse_Table();
Log[1]=0;
for(int i=2; i<=step; i++)Log[i]=Log[i>>1]+1;
Min=INT_MAX;
Get_Root(1,0,n);
Root=root;
build(root);
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
for(int i=x; i; i=father[i])val1[i]+=y*dist(x,i),num[i]+=y;
for(int i=x; father[i]; i=father[i])val2[i]+=y*dist(x,father[i]);
printf("%lld\n",Query());
}
return 0;
}
