果然点分治这种东西跑不过树剖啊（
首先，有一个结论：最优的补给站的位置就是树的重心，不过原来的子树大小要换成子树点权和。
证明：假设最优解是一个在重心以外的点 \(x\)，令其向重心移动一步。设走过的这条边边权为 \(w\)，会走到 \(y\)。
那么会发现在 \(y\) 那边的点的贡献全部少了 \(w\)，在 \(x\) 这边的点的贡献全部多了 \(w\)。
由于 \(x\) 不是重心，所以 \(y\) 那边的点权和一定大于 \(x\) 这边的点权和。
故越接近重心解就更优，最优解即重心。
求重心比较简单，根据重心的性质，其实重心就是满足 \(2size_x \ge size_{root}\) 的最深的 \(x\)。其中 \(root\) 表示树根。
在线段树上根据 DFS 序维护 \(size\)，然后直接线段树上二分找最深的即可。
用 DFS 序是因为 DFS 序越大就越深（当然是同一条链上）。
设重心为 \(u\)，那么问题就变成了求 \(\sum\limits_{v = 1}^n d_v \cdot \text{dist}(u,v)\)。
这个其实也挺套路的，首先把路径转化为到根相减，然后分别写成三个和式，得 \[\sum\limits_{v = 1}^n d_v \cdot \text{dist}(root,u) + \sum\limits_{v = 1}^n d_v \cdot \text{dist}(root,v) - 2\sum\limits_{v = 1}^n d_v \cdot \text{dist}(root,\text{lca}(u,v))\]
前两个和式很方便维护，重点在于第三个。
考虑 \(u\) 到根路径上的一个点 \(x\) 到其一个儿子 \(y\) 的一条边权为 \(w\) 的边，显然它会影响 \(y\) 子树内的所有点的贡献，即 \(w \cdot size_y\)。因为这些点和 \(u\) 的 \(\text{lca}\) 到根的路径必然会经过这条边。
于是令 \(w_p\) 表示 \(p\) 到其父亲的边权，最后一个和式其实就是对 \(u\) 到根路径上的每一个点 \(x\)，求出 \(size_x \cdot w_x\) 之和。
修改时需要改动 \(size\)，实际上改动的就是该点到根的路径上的 \(size\)。
线段树和树剖维护即可。
代码： 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
using namespace std;
const int N = 1e5;
int n,q;
int to[(N << 1) + 5],val[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v,int w)
{
static int tot = 0;
to[++tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],id[N + 5],rk[N + 5];
int w[N + 5];
long long dis[N + 5];
long long sum_d,sum_d_dis;
void dfs1(int p)
{
sz[p] = 1;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
fa[to[i]] = p,dep[to[i]] = dep[p] + 1,dis[to[i]] = dis[p] + val[i],w[to[i]] = val[i],dfs1(to[i]),sz[p] += sz[to[i]];
if(!son[p] || sz[son[p]] < sz[to[i]])
son[p] = to[i];
}
}
void dfs2(int p)
{
static int tot = 0;
rk[id[p] = ++tot] = p;
if(son[p])
top[son[p]] = top[p],dfs2(son[p]);
for(register int i = first[p];i;i = pre[i])
if(!id[to[i]])
top[to[i]] = to[i],dfs2(to[i]);
}
struct node
{
int sz,add;
long long sum,w;
} seg[(N << 2) + 10];
void build(int p,int tl,int tr)
{
if(tl == tr)
{
seg[p].w = w[rk[tl]];
return ;
}
int mid = tl + tr >> 1;
build(ls,tl,mid),build(rs,mid + 1,tr);
seg[p].w = seg[ls].w + seg[rs].w;
}
void update(int l,int r,int k,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
{
seg[p].sz += k,seg[p].add += k,seg[p].sum += seg[p].w * k;
return ;
}
int mid = tl + tr >> 1;
l <= mid && (update(l,r,k,ls,tl,mid),1);
r > mid && (update(l,r,k,rs,mid + 1,tr),1);
seg[p].sz = max(seg[ls].sz,seg[rs].sz) + seg[p].add;
seg[p].sum = seg[ls].sum + seg[rs].sum + seg[p].w * seg[p].add;
}
pair<long long,long long> operator+(pair<long long,long long> a,pair<long long,long long> b)
{
return make_pair(a.first + b.first,a.second + b.second);
}
pair<long long,long long> query(int l,int r,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
return make_pair(seg[p].sum,seg[p].w);
pair<long long,long long> ret = make_pair(0,0);
int mid = tl + tr >> 1;
l <= mid && (ret = ret + query(l,r,ls,tl,mid),1);
r > mid && (ret = ret + query(l,r,rs,mid + 1,tr),1);
ret.first += ret.second * seg[p].add;
return ret;
}
int query(int add,int p,int tl,int tr)
{
if(tl == tr)
return rk[tl];
int mid = tl + tr >> 1;
if((seg[rs].sz + add + seg[p].add) * 2 >= seg[1].sz)
return query(add + seg[p].add,rs,mid + 1,tr);
else
return query(add + seg[p].add,ls,tl,mid);
}
void update(int x,int k)
{
for(;x;x = fa[top[x]])
update(id[top[x]],id[x],k,1,1,n);
}
long long query(int x)
{
long long ret = 0;
for(;x;x = fa[top[x]])
ret += query(id[top[x]],id[x],1,1,n).first;
return ret;
}
int main()
{
scanf("%d%d",&n,&q);
int u,v,w;
for(register int i = 1;i < n;++i)
scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
dep[1] = top[1] = 1,dfs1(1),dfs2(1),build(1,1,n);
int x,k;
for(;q;--q)
{
scanf("%d%d",&x,&k);
sum_d += k,sum_d_dis += dis[x] * k,update(x,k);
int p = query(0,1,1,n);
printf("%lld\n",sum_d_dis + sum_d * dis[p] - 2 * query(p));
}
}