有一颗带权树,有三个操作:
- 给一个点打上标记。
- 删除一个点的标记。
- 查询有标记的点的导出子树的边权和。
\(n, q \le 10^5\)。
求的实际上就是虚树的大小,求这个有一个常用的方法就是把点按 dfn 排序后相邻点对(首尾也算相邻)之间的距离和除以 2。
所以我们可以维护一个 set,然后每次插入删除点的时候顺便求一下与它相邻的点的距离加上或者减去就行。
时间复杂度 \(O(n \log n)\)。
constexpr int MAXN = 1e5 + 9, MAXLG = 17;
int n, m, fa[MAXLG][MAXN], dep[MAXN], dfn[MAXN],
id[MAXN];
vpii G[MAXN];
ll dis[MAXN], ans = 0;
set<int> s;
void dfs(int u, int fa) {
static int dfc = 0; id[dfn[u] = ++ dfc] = u;
dep[u] = dep[::fa[0][u] = fa] + 1;
for (int i = 1; i <= 16; i ++)
::fa[i][u] = ::fa[i - 1][::fa[i - 1][u]];
for (auto [v, w] : G[u]) {
if (v == fa) continue;
dis[v] = dis[u] + w, dfs(v, u);
}
return;
}
int Get_Lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = 16; ~i; i --)
if (dep[fa[i][u]] >= dep[v])
u = fa[i][u];
if (u == v) return u;
for (int i = 16; ~i; i --)
if (fa[i][u] ^ fa[i][v])
u = fa[i][u], v = fa[i][v];
return fa[0][u];
}
ll Get_Dis(int u, int v) {
int lca = Get_Lca(u, v);
return dis[u] + dis[v] - 2 * dis[lca];
}
void slv() {
n = Read<int>();
for (int i = 1; i < n; i ++) {
int u = Read<int>(), v = Read<int>(), w = Read<int>();
G[u].emplace_back(v, w), G[v].emplace_back(u, w);
}
dfs(1, 0);
auto pre = [&](int x) {
auto it = s.lower_bound(dfn[x]);
if (it == s.begin()) it = s.end();
return id[*(-- it)];
};
auto suf = [&](int x) {
auto it = s.upper_bound(dfn[x]);
if (it == s.end()) it = s.begin();
return id[*it];
};
m = Read<int>();
while (m --) {
char opt[5]; Read(opt);
if (opt[0] == '+') {
int x = Read<int>(); s.insert(dfn[x]);
int u = pre(x), v = suf(x);
ans += Get_Dis(u, x) + Get_Dis(x, v) - Get_Dis(u, v);
} else if (opt[0] == '-') {
int x = Read<int>();
int u = pre(x), v = suf(x); s.erase(dfn[x]);
ans -= Get_Dis(u, x) + Get_Dis(x, v) - Get_Dis(u, v);
}
else Write(ans >> 1, '\n');
}
return;
}