虚树
title: 虚树
categories:
- ICPC
tags:
- null
abbrlink: c15ecfc4
date: 2024-07-11 00:00:00
虚树
模板：
struct edge {
int v, w;
};
struct HLD {
int n;
vector<int> siz, top, parent, l, r, hson, dep;
vector<vector<edge>> adj;
int idx;
vector<int> mn;//1-u的最小边权
HLD() {}
HLD(int n) {
init(n);
}
void init(int n) {
this->n = n;
siz.resize(n + 1), hson.resize(n + 1), top.resize(n + 1);
parent.resize(n + 1);
l.resize(n + 1), r.resize(n + 1);
idx = 0;
adj.resize(n + 1), dep.resize(n + 1);
// 根据题目要求加数据结构
mn.resize(n + 1, 1e9);
}
void addEdge(int u, int v, int w) {
adj[u].push_back({v, w});
}
void work(int root = 1) {
top[root] = root;
parent[root] = -1;
dep[root] = 1;
dfs1(root, -1);
dfs2(root, root);
}
void dfs1(int u, int f) { // 搞fa,dep,son
siz[u] = 1;
for (auto [v, w] : adj[u]) {
if (v == f)
continue;
mn[v] = min(mn[u], w);
parent[v] = u;
dep[v] = dep[u] + 1;
dfs1(v, u);
siz[u] += siz[v];
if (siz[hson[u]] < siz[v])
hson[u] = v;
}
}
void dfs2(int u, int t) { // 搞top
top[u] = t; // 记录链头
l[u] = ++idx;
if (!hson[u]) {
r[u] = idx;
return;
} // 无重儿子
dfs2(hson[u], t); // 搜重儿子
for (auto [v, w] : adj[u]) {
if (v == parent[u] || v == hson[u])
continue;
dfs2(v, v); // 搜轻儿子
}
r[u] = idx;
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
u = parent[top[u]];
} else {
v = parent[top[v]];
}
}
return dep[u] < dep[v] ? u : v;
}
bool isAncester(int u, int v) { // 判断u是不是v的祖先
return l[u] <= l[v] && r[v] <= r[u];
}
};
void solve() {
int n;
cin >> n;
HLD hld(n);
for (int i = 1; i <= n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
hld.addEdge(u, v, w);
hld.addEdge(v, u, w);
}
auto cmp = [&](int i, int j) {
return hld.l[i] < hld.l[j];
};
hld.work(1);
auto buildvt = [&](vector<int>& node, vector<vector<edge>>& e) {
node.push_back(1);//保证根节点在虚树中存在
sort(alls(node), cmp);
node.erase(unique(alls(node)), node.end());
set<int> tmp;
for (auto x : node) tmp.insert(x);
for (int i = 1; i < (int)node.size(); i++) tmp.insert(hld.lca(node[i - 1], node[i]));
node.clear();
for (auto x : tmp) node.push_back(x);
sort(alls(node), cmp);
vector<int> st; // 维护一个栈
for (auto v : node) {
while (!st.empty() && !hld.isAncester(st.back(), v))
st.pop_back();
if (!st.empty())
e[st.back()].push_back({v, hld.mn[v]});
st.push_back(v);
}
};
int q;
cin >> q;
vector<vector<edge>> e(n + 1);
vector<ll> dp(n + 1); // 使得u子树内关键点与u不连通的代价
vector<bool> vis(n + 1);
auto cal = [&](auto self, int u, int fa) -> void {//计算答案
for (auto [v, w] : e[u]) {
if (v == fa)
continue;
self(self, v, u);
if (vis[v])
dp[u] += w;
else
dp[u] += min((ll)w, dp[v]);
}
};
auto clear = [&](vector<int>& node) {//清空本次用的点的信息
for (auto x : node) {
vis[x] = 0;
dp[x] = 0;
e[x].clear();
}
};
for (int i = 1; i <= q; i++) {
int num;
cin >> num;
vector<int> node;
for (int j = 1; j <= num; j++) {
int x;
cin >> x;
node.push_back(x);
vis[x] = 1;
}
buildvt(node, e);
cal(cal, 1, 1);
cout << dp[1] << endl;
clear(node);
}
}
虚数建树模板题[P245 SDOI2011] 消耗战 - 洛谷 | 计算机科学教育新生态
题意：给定一颗树，q次查询，每次查询k个点，每个边有砍断的代价，求最少砍断多少条边使得这k个点都无法到达1号根节点。保证 $\sum k \le2e5$
Sol：对于这样的询问点集总和有$\sum$保证的，可以考虑虚树。对于k个关键点，虚数最多2k个点，这样总和还是$O(\sum k)$级别的，复杂度有了保证。我们应该考虑问题的核心是如何dp。考虑$dp[u]$表示以u为根的子树中没有关键点与u连通的最小代价。
- 转移如下：对于u的儿子v，如果v是关键节点，那u和v之间的边必须切断。如果v不是关键节点，那考虑可以递归到dp[v]也可也选择下面的不动，切断这里，也就是$min(dp[v],w)$
实现细节：不能每次动态开边集vector和vis，而是要选择动态清空保证复杂度，实现clear函数。
代码z
应用：Kingdom and its Cities - 洛谷 | 计算机科学教育新生态
1.题意：给定一棵树。q次查询，每次查询给出k个关键点，现在需要消灭一些非关键点使得这k个点两两不连通，求最小消灭点的数量满足需求。($\sum k \le 1e5$)
Sol：还是可以建立虚数，然后我们考虑怎么dp。考虑$dp[u]$表示考虑u的子树内关键点互相都不连通的代价。
- u本身是关键点，则它的任意一个儿子里面有剩余未处理干净的关键点的话 ，必须选择切断下面的这个儿子。说到这里自然会考虑如果儿子也是关键点呢，我们只能消灭非关键点，所以这种情况我们是无法处理的，无解。
- 所以无解的情况就是存在两个关键点直接有边相连
- u不是关键点，那不能出现u内有两个儿子内部通过u连通，一旦出现就需要把u消灭掉，同时把dp[u]=0表示u的子树已经处理完了，上面考虑的时候不会重复计算这部分。
void solve() {
int n;
cin >> n;
HLD hld(n);
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
hld.addEdge(u, v);
hld.addEdge(v, u);
}
auto cmp = [&](int i, int j) {
return hld.l[i] < hld.l[j];
};
hld.work(1);
auto buildvt = [&](vector<int>& node, vector<vector<int>>& e) {
node.push_back(1);
sort(alls(node), cmp);
node.erase(unique(alls(node)), node.end());
set<int> tmp;
for (auto x : node) tmp.insert(x);
for (int i = 1; i < (int)node.size(); i++) tmp.insert(hld.lca(node[i - 1], node[i]));
node.clear();
for (auto x : tmp) node.push_back(x);
sort(alls(node), cmp);
deb(node);
vector<int> st; // 维护一个栈
for (auto v : node) {
deb(st, v);
while (!st.empty() && !hld.isAncester(st.back(), v))
st.pop_back();
if (!st.empty())
e[st.back()].push_back(v);
st.push_back(v);
}
};
int q;
cin >> q;
int ans = 0;
vector<int> sz(n + 1);
vector<vector<int>> e(n + 1);
// 考虑以u子树内所有关键点不连通的代价
function<void(int, int)> dp = [&](int u, int fa) {
if (sz[u]) { // 本身是关键点
for (auto v : e[u]) {
if (v == fa)
continue;
dp(v, u);
if (sz[v]) {
ans++;
sz[v] = 0;
}
}
} else {
for (auto v : e[u]) {
if (v == fa)
continue;
deb(u, v);
dp(v, u);
sz[u] += sz[v];
sz[v] = 0; // 清空
}
if (sz[u] >= 2) {
ans++;
sz[u] = 0;
}
}
};
auto clear = [&](vector<int>& node) {
for (auto x : node) e[x].clear(), sz[x] = 0;
ans = 0;
};
for (int i = 1; i <= q; i++) {
int num;
cin >> num;
vector<int> node;
for (int j = 1; j <= num; j++) {
int x;
cin >> x;
node.push_back(x);
sz[x] = 1;
}
// 提前特判无解情况------------------
bool flag = true;
for (auto x : node) {
if (x == 1)
continue;
int fa = hld.parent[x];
if (sz[fa] > 0) {
cout << -1 << endl;
flag = false;
break;
}
}
if (flag == 0) {
clear(node);
continue;
}
//----------------------------------
buildvt(node, e);
dp(1, 1);
cout << ans << endl;
for (auto x : node) e[x].clear(), sz[x] = 0;
clear(node);
}
}
2.https://atcoder.jp/contests/abc359/tasks/abc359_g
题意：树上每个点有自己的颜色，定义$f(i,j)=[color[i]==color[j]] \times dis(i,j)$
求$\displaystyle \sum _ {i=1}^{N-1}\sum _ {j=i+1}^N f(i,j)$(启发式合并做法待补，jiangly)
考虑相同颜色的点之间才有贡献，按照把相同颜色的点放一起建立虚树，虚数的边权为两个点的深度差。考虑一个边的贡献次数就是联通块两侧数量乘积。
void solve() {
int n;
cin >> n;
HLD hld(n);
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
hld.addEdge(u, v, 1);
hld.addEdge(v, u, 1);
}
vector<int> a(n + 1);
vector<vector<int>> q(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i], q[a[i]].push_back(i);
auto cmp = [&](int i, int j) {
return hld.l[i] < hld.l[j];
};
hld.work(1);
auto buildvt = [&](vector<int>& node, vector<vector<edge>>& e, int rt) {
node.push_back(rt); // 保证根节点在虚树中存在
sort(alls(node), cmp);
node.erase(unique(alls(node)), node.end());
set<int> tmp;
for (auto x : node) tmp.insert(x);
for (int i = 1; i < (int)node.size(); i++) tmp.insert(hld.lca(node[i - 1], node[i]));
node.clear();
for (auto x : tmp) node.push_back(x);
sort(alls(node), cmp);
vector<int> st; // 维护一个栈
for (auto v : node) {
while (!st.empty() && !hld.isAncester(st.back(), v))
st.pop_back();
if (!st.empty())
e[st.back()].push_back({v, hld.dep[v] - hld.dep[st.back()]});
st.push_back(v);
}
};
vector<vector<edge>> e(n + 1);
vector<int> sz(n + 1);
ll ans = 0;
int sum = 0;
function<void(int, int)> calsz = [&](int u, int fa) {
for (auto [v, w] : e[u]) {
if (v == fa)
continue;
calsz(v, u);
sz[u] += sz[v];
}
};
function<void(int, int)> cal = [&](int u, int fa) {
for (auto [v, w] : e[u]) {
if (v == fa)
continue;
cal(v, u);
ans += (ll)sz[v] * (sum - sz[v]) * w;
}
};
auto clear = [&](vector<int>& node) {
for (auto x : node) {
e[x].clear();
sz[x] = 0;
}
};
deb(a);
for (int i = 1; i <= n; i++) {
vector<int> node;
for (auto x : q[i]) node.push_back(x), sz[x] = 1;
deb(node);
sum = node.size();
buildvt(node, e, 1);
calsz(1, 1);
cal(1, 1);
clear(node);
}
cout << ans << endl;
}
3.给定一棵树，树上每个点有自己的颜色。求满足条件1和2的树的导出子图数量
- 导出子图还是树
- 导出子图所有度为1的点都是相同颜色的
Sol：颜色相同想到虚树，枚举 导出子图T叶子的颜色 C ， T 一定是这个颜色的点构成的虚树的子图。
dp统计答案。$f[u]$表示 u 作为 当前子图树的根的时候有$ f[u] $种合法方案。
- 考虑转移：对于儿子v，选有$f[v]$种方案，不选是1种方案。$f[u]^{*}=f[v]+1$。写到这里发现需要讨论，因为如果都不选就剩u一个点的话，u必须是颜色C才行。
- u就是C颜色，那可以向答案直接贡献$f[u]$
- u不是c颜色，首先u不能作为度数为1的点。首先就是不能只选u一个点，$f[u]-=1$。其次再考虑就是不能只选一个儿子，这时候u的度数也只有1.
为了更加清晰，不妨引入$g[u]$,它表示u只选一个儿子的方案数。
$f_{u}=∏{v∈sonu}(f{v}+1)−[coloru=C],$
$g_{u}=∑{v∈son[u]}f{v}$
void solve() {
int n;
cin >> n;
HLD hld(n);
vector<vector<int>> q(n + 1);
vector<int> col(n + 1);
for (int i = 1; i <= n; i++) {
cin >> col[i];
q[col[i]].push_back(i);
}
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
hld.addEdge(u, v, 1);
hld.addEdge(v, u, 1);
}
vector<int> a(n + 1);
auto cmp = [&](int i, int j) {
return hld.l[i] < hld.l[j];
};
hld.work(1);
auto buildvt = [&](vector<int>& node, vector<vector<edge>>& e, int rt) {
node.push_back(rt); // 保证根节点在虚树中存在
sort(alls(node), cmp);
node.erase(unique(alls(node)), node.end());
set<int> tmp;
for (auto x : node) tmp.insert(x);
for (int i = 1; i < (int)node.size(); i++) tmp.insert(hld.lca(node[i - 1], node[i]));
node.clear();
for (auto x : tmp) node.push_back(x);
sort(alls(node), cmp);
vector<int> st; // 维护一个栈
for (auto v : node) {
while (!st.empty() && !hld.isAncester(st.back(), v))
st.pop_back();
if (!st.empty())
e[st.back()].push_back({v, hld.dep[v] - hld.dep[st.back()]});
st.push_back(v);
}
};
vector<vector<edge>> e(n + 1);
vector<int> f(n + 1), g(n + 1);
auto clear = [&](vector<int>& node) {
for (auto x : node) {
e[x].clear();
f[x] = g[x] = 0;
}
};
int cur = 0;
int ans = 0;
function<void(int, int)> cal = [&](int u, int fa) {
f[u] = 1;
g[u] = 0;
for (auto [v, w] : e[u]) {
if (v == fa)
continue;
cal(v, u);
f[u] *= f[v] + 1;
f[u] %= mod;
g[u] += f[v];
}
if (col[u] == cur) {
ans += f[u];
} else {
f[u] = (f[u] + mod - 1) % mod;
ans += (f[u] + mod - g[u]) % mod;
ans %= mod;
}
};
for (int i = 1; i <= n; i++) {
vector<int> node;
for (auto x : q[i]) node.push_back(x);
deb(node);
buildvt(node, e, 1);
cur = i;
cal(1, 1);
clear(node);
}
cout << ans << endl;
}
Sol：对于权值和已经在例题2叙述过了。最大值和最小值总体思路一样。先预处理 maxdep[u]表示距离u的子树里距离u最远的关键点。再考虑resmn[u]表示u的子树里最长路径，找到u的最深链mx1，次深链mx2(考虑叶子一定是关键点)。$resmn[u]=max(resmn[v],mx1+mx2)$.
说到这里我们需要思考最小路径不一定是从叶子开始，我们不能完全模仿同样维护mn1和mn2.因为最短路径没有必要从叶子开始。所以需要提前处理的是对于关键节点keynode打标记，而在虚树上的lca非关键节点不标记。具体来说$mindep[keynode]=0以及最小链mn1=0$
实现方面：加入chmax便于取max，同时要注意维护次大值。MLE是因为#define int long long
bool chmax(int& fir, int sec) {
if (sec > fir) {
fir = sec;
return true;
}
return false;
}
bool chmin(int& fir, int sec) {
if (sec < fir) {
fir = sec;
return true;
}
return false;
}
struct edge {
int v, w;
};
struct HLD {
int n;
vector<int> siz, top, parent, l, r, hson, dep;
vector<vector<edge>> adj;
int idx;
vector<int> mn; // 1-u的最小边权
HLD() {}
HLD(int n) {
init(n);
}
void init(int n) {
this->n = n;
siz.resize(n + 1), hson.resize(n + 1), top.resize(n + 1);
parent.resize(n + 1);
l.resize(n + 1), r.resize(n + 1);
idx = 0;
adj.resize(n + 1), dep.resize(n + 1);
// 根据题目要求加数据结构
}
void addEdge(int u, int v, int w) {
adj[u].push_back({v, w});
}
void work(int root = 1) {
top[root] = root;
parent[root] = -1;
dep[root] = 1;
dfs1(root, -1);
dfs2(root, root);
}
void dfs1(int u, int f) { // 搞fa,dep,son
siz[u] = 1;
for (auto [v, w] : adj[u]) {
if (v == f)
continue;
parent[v] = u;
dep[v] = dep[u] + 1;
dfs1(v, u);
siz[u] += siz[v];
if (siz[hson[u]] < siz[v])
hson[u] = v;
}
}
void dfs2(int u, int t) { // 搞top
top[u] = t; // 记录链头
l[u] = ++idx;
if (!hson[u]) {
r[u] = idx;
return;
} // 无重儿子
dfs2(hson[u], t); // 搜重儿子
for (auto [v, w] : adj[u]) {
if (v == parent[u] || v == hson[u])
continue;
dfs2(v, v); // 搜轻儿子
}
r[u] = idx;
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
u = parent[top[u]];
} else {
v = parent[top[v]];
}
}
return dep[u] < dep[v] ? u : v;
}
bool isAncester(int u, int v) { // 判断u是不是v的祖先
return l[u] <= l[v] && r[v] <= r[u];
}
};
void solve() {
int n;
cin >> n;
HLD hld(n);
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
hld.addEdge(u, v, 1);
hld.addEdge(v, u, 1);
}
auto cmp = [&](int i, int j) {
return hld.l[i] < hld.l[j];
};
hld.work(1);
auto buildvt = [&](vector<int>& node, vector<vector<edge>>& e, int rt) {
node.push_back(rt); // 保证根节点在虚树中存在
sort(alls(node), cmp);
node.erase(unique(alls(node)), node.end());
set<int> tmp;
for (auto x : node) tmp.insert(x);
for (int i = 1; i < (int)node.size(); i++) tmp.insert(hld.lca(node[i - 1], node[i]));
node.clear();
for (auto x : tmp) node.push_back(x);
sort(alls(node), cmp);
vector<int> st; // 维护一个栈
for (auto v : node) {
while (!st.empty() && !hld.isAncester(st.back(), v))
st.pop_back();
if (!st.empty())
e[st.back()].push_back({v, hld.dep[v] - hld.dep[st.back()]});
st.push_back(v);
}
};
vector<vector<edge>> e(n + 1);
vector<int> sz(n + 1);
vector<bool> vis(n + 1);
vector<int> ressz(n + 1), resmn(n + 1, inf), resmx(n + 1); // u子树内最大值，最小值
ll ans = 0;
int sum = 0;
vector<int> maxdep(n + 1), mindep(n + 1, inf);
function<void(int, int)> precal = [&](int u, int fa) {
for (auto [v, w] : e[u]) {
if (v == fa)
continue;
deb(u, v);
precal(v, u);
sz[u] += sz[v];
chmin(mindep[u], mindep[v] + w);
chmax(maxdep[u], maxdep[v] + w);
}
deb(u, sz[u]);
deb(u, mindep[u]);
deb(u, maxdep[u]);
};
function<void(int, int)> cal = [&](int u, int fa) {
int mn1 = inf, mn2 = inf;
int mx1 = 0, mx2 = 0;
if (vis[u])
mn1 = 0;
for (auto [v, w] : e[u]) {
if (v == fa)
continue;
cal(v, u);
ans += (ll)sz[v] * (sum - sz[v]) * w;
int tmp1 = mn1, tmp2 = mx1;
if (chmin(mn1, mindep[v] + w) == 0)
chmin(mn2, mindep[v] + w);
else {
mn2 = tmp1;
}
if (chmax(mx1, maxdep[v] + w) == 0)
chmax(mx2, maxdep[v] + w);
else {
mx2 = tmp2;
}
chmin(resmn[u], resmn[v]);
chmax(resmx[u], resmx[v]);
deb(u, v, mn1, mn2);
}
deb(u, mn1, mn2);
deb(u, mx1, mx2);
if (vis[u] || (mn1 < inf && mn2 < inf))
chmin(resmn[u], mn1 + mn2);
if (vis[u] || (mx1 > 0 && mx2 > 0))
chmax(resmx[u], mx1 + mx2);
};
auto clear = [&](vector<int>& node) {
for (auto x : node) {
e[x].clear();
sz[x] = 0;
resmn[x] = inf;
resmx[x] = 0;
maxdep[x] = 0;
mindep[x] = inf;
vis[x] = 0;
}
ans = 0;
};
int q;
cin >> q;
for (int i = 1; i <= q; i++) {
vector<int> node;
int num;
cin >> num;
for (int j = 1; j <= num; j++) {
int x;
cin >> x;
node.push_back(x);
sz[x] = 1;
vis[x] = 1;
mindep[x] = 0;
}
deb(node);
sum = node.size();
buildvt(node, e, 1);
precal(1, 1);
cal(1, 1);
cout << ans << " " << resmn[1] << " " << resmx[1] << endl;
clear(node);
deb("end");
}
}
5.https://codeforces.com/gym/104128/problem/E
长剖做法： [【2022icpc Regional 南京 E】Color the Tree 题解 | Four’s](http://kqp.world/【2022icpc Regional 南京 E】Color the Tree 题解/index.html)
虚数题解：Color the Tree-虚树(2022南京区域赛) - 知乎
题意：给你一棵根树，根节点为 1 ，起初树的所有节点的颜色都是白色，你需要将每个节点染成黑色，你可以执行以下操作任意次：
- 从树中任选一个点 u
- 选定一个数字 $d(0≤d≤n−1) $，将 u 的子树中与其距离为 d 的点都涂黑
一次操作的代价为 a[d] ， a 数组已经给出，求将所有点涂黑的最小花费。
Sol:具体更详细可以见sua——wiki。考虑染黑每一层是独立的，所以我们对每一层单独考虑贡献。这一层下面的点此时就没有用，我们考虑对这一层的点建立虚树。核心是考虑怎么dp？考虑染黑第cur层
- $dp[u]$表示考虑以u为根的子树染黑这一层的贡献。u本身花费$a[cur-dep[u]]$的代价如果染，就会完成所有任务，任何儿子都不参与是最优的。不染的话就全都交给子节点去做，然后由于是虚树，相邻两点的边本质上是一条链，所以我们需要$tmp+=min(dp[v],min[a[cur-dep[v]],a[cur-dep[u]-1]])$
- 实现上需要特判叶子的情况，主要是对于tmp的赋初始值
void solve() {//此处省略状压rmq板子和h
int n;
cin >> n;
HLD hld(n);
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
RMQ<int> qmn(a);
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
hld.addEdge(u, v, 1);
hld.addEdge(v, u, 1);
}
auto cmp = [&](int i, int j) {
return hld.l[i] < hld.l[j];
};
hld.work(1);
auto buildvt = [&](vector<int>& node, vector<vector<edge>>& e, int rt) {
node.push_back(rt); // 保证根节点在虚树中存在
sort(alls(node), cmp);
node.erase(unique(alls(node)), node.end());
set<int> tmp;
for (auto x : node) tmp.insert(x);
for (int i = 1; i < (int)node.size(); i++) tmp.insert(hld.lca(node[i - 1], node[i]));
node.clear();
for (auto x : tmp) node.push_back(x);
sort(alls(node), cmp);
vector<int> st; // 维护一个栈
for (auto v : node) {
while (!st.empty() && !hld.isAncester(st.back(), v))
st.pop_back();
if (!st.empty())
e[st.back()].push_back({v, hld.dep[v] - hld.dep[st.back()]});
st.push_back(v);
}
};
vector<vector<edge>> e(n + 1);
vector<vector<int>> q(n + 1);
int maxdep = 0;
for (int i = 1; i <= n; i++) q[hld.dep[i]].push_back(i), maxdep = max(maxdep, hld.dep[i]);
ll ans = 0;
vector<ll> dp(n + 1, 1e18);
int cur = 0;
function<void(int, int)> cal = [&](int u, int fa) {
ll tmp = 0;
if (e[u].size() == 0)
tmp = 1e18;
for (auto [v, w] : e[u]) {
if (v == fa)
continue;
deb(u, v);
cal(v, u);
int ql = cur - hld.dep[v];
int qr = cur - hld.dep[u] - 1;
tmp += min(dp[v], (ll)qmn(ql, qr + 1));
}
dp[u] = min(tmp, (ll)a[cur - hld.dep[u]]); // +1是深度偏移
};
auto clear = [&](vector<int>& node) {
for (auto x : node) {
e[x].clear();
dp[x] = 1e18;
}
};
for (int i = 1; i <= maxdep; i++) {
vector<int> node;
for (auto x : q[i]) node.push_back(x);
cur = i;
deb(i, node);
buildvt(node, e, 1);
cal(1, 1);
deb(dp[1]);
ans += dp[1];
clear(node);
deb("end");
}
cout << ans << endl;
}
6.Problem - 1681F - Codeforces题意:给定一棵树,边有边权。定义$f(u,v)为u到v简单路径上只出现一次的边权的权值数量$
参考学习:https://www.luogu.com.cn/article/dad36cgq（待补可撤销并查集以及线段树分治）
Sol：先考虑朴素做法。把所有颜色c的边砍去，答案就是相邻联通块大小乘积。这个是因为如果一条路径进入了大于两个「联通块」，那么就会出现两条颜色为 c的边。但这样枚举边的颜色，再dp统计的时间复杂度不对。
考虑颜色相关的均摊，想到虚树做法。每个值贡献独立，枚举边颜色cur，把边权两端的点全部抽出来建立虚树。
- $sf[i] 代表 i 子树内和 i 在同个「联通块」的有几个点。$
- $ot[i]代表 i 子树内与 i相邻的「联通块」的大小总和。$
$$ {转移如下：}
\begin{align*}
转移：
sf_u &= \sum sf_v [w = c] + \text{size}_u - \sum \text{size}_v \
ot_u &= \sum ot_v [w \neq c] + \sum sf_v [w = c]
\end{align*}
$$
sf的前面部分是虚树上所有和它在同个「联通块」的儿子的子树贡献
ss 的后面部分是不在虚树上的点的个数的贡献
$ot_{u}$的前面部分是和它在同个「联通块」的儿子的子树贡献，考虑u和v在同一联通块，则要统计与自己不在一起的联通块大小递归到和儿子不在一起的$ot_{v}$。
$ot_{u}$的后面部分是和它在不同「联通块」的儿子的联通块贡献。考虑u和v不在同一联通块，则要统计与自己不在一起的联通块大小递归到和儿子在一起的$sf_{v}$。
最后统计答案，应该是每个「联通块」的根(最高点），把自己的「联通块」的大小乘上身边「联通块」的大小总和，形式化地，
$res=∑sf_{u}ot_{u}[u=rt \or w(u,fau)=c]$
实现细节：建立虚树的时候需要加边，这关系到在哪里统计答案。需要开set或者map去记录这两点之间存不存在颜色为c的边，因为是虚树，两个点之间可能没什么关系，所以要支持快速随机访问。
void solve() {
int n;
cin >> n;
HLD hld(n);
vector<vector<int>> col(n + 1);
vector<set<pii>> findedge(n + 1);
for (int i = 1; i <= n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
hld.addEdge(u, v, w);
hld.addEdge(v, u, w);
col[w].push_back(u);
col[w].push_back(v);
findedge[w].insert({min(u, v), max(u, v)});
}
auto cmp = [&](int i, int j) {
return hld.l[i] < hld.l[j];
};
hld.work(1);
int cur = 0;
vector<vector<edge>> e(n + 1);
vector<int> sf(n + 1), ot(n + 1);
ll ans = 0;
auto buildvt = [&](vector<int>& node, vector<vector<edge>>& e, int rt) {
node.push_back(rt); // 保证根节点在虚树中存在
sort(alls(node), cmp);
node.erase(unique(alls(node)), node.end());
deb(cur);
deb(node);
set<int> tmp;
for (auto x : node) tmp.insert(x);
for (int i = 1; i < (int)node.size(); i++) tmp.insert(hld.lca(node[i - 1], node[i]));
node.clear();
for (auto x : tmp) node.push_back(x);
sort(alls(node), cmp);
vector<int> st; // 维护一个栈
for (auto v : node) {
while (!st.empty() && !hld.isAncester(st.back(), v))
st.pop_back();
if (!st.empty()) {
int w = 0;
int mn = min(st.back(), v), mx = max(st.back(), v);
if (findedge[cur].count({mn, mx}))
w = cur;
e[st.back()].push_back({v, w});
}
st.push_back(v);
}
};
function<void(int, int)> cal = [&](int u, int fa) {
sf[u] = hld.siz[u];
for (auto [v, w] : e[u]) {
if (v == fa)
continue;
cal(v, u);
if (w == cur) {
ans += (ll)sf[v] * ot[v];
}
sf[u] += (w != cur) * sf[v] - hld.siz[v];
ot[u] += (w == cur) * sf[v] + (w != cur) * ot[v];
}
};
auto clear = [&](vector<int>& node) {
for (auto x : node) {
e[x].clear();
sf[x] = ot[x] = 0;
}
};
for (int i = 1; i <= n; i++) {
if (col[i].size() == 0)
continue;
vector<int> node;
for (auto x : col[i]) node.push_back(x);
cur = i;
buildvt(node, e, 1);
cal(1, 1);
ans += (ll)sf[1] * ot[1];
clear(node);
}
cout << ans << endl;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！