TIOJ-1171

發表於 更新於 Disqus：

給一棵$N$個節點的樹(每條邊有權重$L_i$)，每個節點都是白色，以及$Q$筆操作。

1 x – 將點$x$塗成黑色

2 x – 詢問點$x$到所有黑點的總和

$1\le N\le 10^5, 1\le Q\le 10^6, 1\le L_i\le 10^7$

重心剖分的經典題
將點$x$到其他點的路徑以$x$到該點的LCA分類，可以發現那些LCA正好會是$x$在重心樹上的祖先。

令$sum_{u, v}$為重心樹上$u$為根節點的子樹裡黑點到$v$的總和，$cnt_u$為子樹內黑點的數量，$d_{u, v}$為$u$到$v$的距離

若詢問的點為$x$，且令$q$為$p$在重心樹上的父節點($p$為$x$在重心樹上的所有祖先)，可以推出式子:
$$\sum (sum_{q, q} - sum_{p, q}) + (cnt_q - cnt_p) \times d_{x, q})$$
基本上就是不斷計算以$q$當根的答案，但還要扣掉自己所在的子樹($p$)的答案

修改時可以很輕鬆地計算$sum_{q, q}$和$cnt_q$。

而$d_{u, v}$可以在重心剖分時時暴力跑dfs。

最麻煩的是$sum_{p, q}$，因為重心樹上的父子關係不等於原圖，所以$sum_{p, q}=sum_{p, p} + d_{p, q}\times cnt_p$這式子是不成立的。

解決方法就是注意到$p$總是$q$的子節點(在重心樹上)，所以可以令$no_p = sum_{p, q}$，在將$x$塗色時時同時將$no_p$加上$d_{x, q}$就好。

複雜度$\mathcal{O}((N+Q)logN)$。

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
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*--------------------------------------------------------------------------------------*/

const int N = 1e5 + 25;

vector<pair<int, int>> edge[N];
int pa[N], sz[N], cnt[N];
ll dis[N], no[N];
vector<ll> pa_dis[N];
bool vis[N], has[N];

int dfs(int u, int p) { // 重心剖分前紀錄子樹size
	sz[u] = 1;
	for(const auto &w : edge[u])
		if(w.first != p && !vis[w.first]) {
			dfs(w.first, u);
			sz[u] += sz[w.first];
		}
	return sz[u];
}
int centroid(int u, int p, int n) { // 尋找重心
	for(const auto &w : edge[u])
		if(!vis[w.first] && w.first != p && sz[w.first] > n / 2)
			return centroid(w.first, u, n);
	return u;
}
void caldis(int u, int p, ll d) { // 計算對於每個點他到重心樹上的所有父節點的距離
	pa_dis[u].push_back(d);
	for(const auto &w : edge[u])
		if(!vis[w.first] && w.first != p)
			caldis(w.first, u, d + w.second);
}
void cd(int u, int p) { // 重心剖分
	int n = dfs(u, u);
	u = centroid(u, u, n);
	vis[u] = 1;
	pa[u] = p;
	caldis(u, u, 0);
	for(const auto &w : edge[u]) {
		if(vis[w.first])
			continue;
		cd(w.first, u);
	}
}
void edt(int u) { // 修改
	int x = u;
	for(int h = 0; ~u; u = pa[u], h++) {
		cnt[u]++;
		dis[u] += pa_dis[x][h];
		if(h < pa_dis[x].size())
			no[u] += pa_dis[x][h + 1]; // no[u]代表在以u為根的子樹在以pa[u]為根的貢獻
	}
}
ll query(int u) {
	ll res = 0, curd = 0;
	int curcnt = 0, x = u;
	for(int h = 0; ~u; u = pa[u], h++) {
		res += (dis[u] - curd) + (cnt[u] - curcnt) * pa_dis[x][h];
		
		curcnt = cnt[u];
		curd = no[u];
	}
	return res;
}

signed main() { EmiliaMyWife
	int n, q;
	cin >> n >> q;
	for(int i = 1, a, b, c; i < n; i++) {
		cin >> a >> b >> c;
		edge[a].push_back({b, c});
		edge[b].push_back({a, c});
	}

	cd(0, -1);
	for(int i = 0; i < n; i++)
		reverse(pa_dis[i].begin(), pa_dis[i].end());

	int t, x;
	while(q--) {
		cin >> t >> x;
		if(t == 1) {
			if(has[x])
				continue;
			has[x] = 1;
			edt(x);
		}
		else
			cout << query(x) << '\n';
	}
}