虚树

模板：

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
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号根节点。保证 ∑k≤2e5\sum k \le2e5

Sol：对于这样的询问点集总和有∑\sum保证的，可以考虑虚树。对于k个关键点，虚数最多2k个点，这样总和还是O(∑k)O(\sum k)级别的，复杂度有了保证。我们应该考虑问题的核心是如何dp。考虑dp[u]dp[u]表示以u为根的子树中没有关键点与u连通的最小代价。

  • 转移如下：对于u的儿子v，如果v是关键节点，那u和v之间的边必须切断。如果v不是关键节点，那考虑可以递归到dp[v]也可也选择下面的不动，切断这里，也就是min(dp[v],w)min(dp[v],w)

实现细节：不能每次动态开边集vector和vis，而是要选择动态清空保证复杂度，实现clear函数。

1
代码z

应用：Kingdom and its Cities - 洛谷 | 计算机科学教育新生态

1.题意：给定一棵树。q次查询，每次查询给出k个关键点，现在需要消灭一些非关键点使得这k个点两两不连通，求最小消灭点的数量满足需求。(∑k≤1e5\sum k \le 1e5)

Sol：还是可以建立虚数，然后我们考虑怎么dp。考虑dp[u]dp[u]表示考虑u的子树内关键点互相都不连通的代价。

  • u本身是关键点，则它的任意一个儿子里面有剩余未处理干净的关键点的话 ，必须选择切断下面的这个儿子。说到这里自然会考虑如果儿子也是关键点呢，我们只能消灭非关键点，所以这种情况我们是无法处理的，无解。
    • 所以无解的情况就是存在两个关键点直接有边相连
  • u不是关键点，那不能出现u内有两个儿子内部通过u连通，一旦出现就需要把u消灭掉，同时把dp[u]=0表示u的子树已经处理完了，上面考虑的时候不会重复计算这部分。
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
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]]×dis(i,j)f(i,j)=[color[i]==color[j]] \times dis(i,j)

求∑i=1N−1∑j=i+1Nf(i,j)\displaystyle \sum _ {i=1}^{N-1}\sum _ {j=i+1}^N f(i,j)(启发式合并做法待补，jiangly)

考虑相同颜色的点之间才有贡献，按照把相同颜色的点放一起建立虚树，虚数的边权为两个点的深度差。考虑一个边的贡献次数就是联通块两侧数量乘积。

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
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]f[u]表示 u 作为 当前子图树的根的时候有$ f[u] $种合法方案。

  • 考虑转移：对于儿子v，选有f[v]f[v]种方案，不选是1种方案。f[u]∗=f[v]+1f[u]^{*}=f[v]+1。写到这里发现需要讨论，因为如果都不选就剩u一个点的话，u必须是颜色C才行。
  • u就是C颜色，那可以向答案直接贡献f[u]f[u]
  • u不是c颜色，首先u不能作为度数为1的点。首先就是不能只选u一个点，f[u]−=1f[u]-=1。其次再考虑就是不能只选一个儿子，这时候u的度数也只有1.

为了更加清晰，不妨引入g[u]g[u],它表示u只选一个儿子的方案数。

fu=∏v∈sonu(fv+1)−[coloru=C],f_{u}=∏_{v∈sonu}(f_{v}+1)−[coloru=C],

gu=∑v∈son[u]fvg_{u}=∑_{v∈son[u]}f_{v}

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
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;
}

4.https://www.luogu.com.cn/problem/P4103题意：给定一棵树，每次选k个点，问这个k个点构成的(2k)\binom{2}{k}条路径的最长路径，最短路径，以及所有路径的权值和。

Sol：对于权值和已经在例题2叙述过了。最大值和最小值总体思路一样。先预处理 maxdep[u]表示距离u的子树里距离u最远的关键点。再考虑resmn[u]表示u的子树里最长路径，找到u的最深链mx1，次深链mx2(考虑叶子一定是关键点)。resmn[u]=max(resmn[v],mx1+mx2)resmn[u]=max(resmn[v],mx1+mx2).

说到这里我们需要思考最小路径不一定是从叶子开始，我们不能完全模仿同样维护mn1和mn2.因为最短路径没有必要从叶子开始。所以需要提前处理的是对于关键节点keynode打标记，而在虚树上的lca非关键节点不标记。具体来说mindep[keynode]=0以及最小链mn1=0mindep[keynode]=0以及最小链mn1=0

实现方面：加入chmax便于取max，同时要注意维护次大值。MLE是因为#define int long long

image-20241023140830861

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
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]dp[u]表示考虑以u为根的子树染黑这一层的贡献。u本身花费a[cur−dep[u]]a[cur-dep[u]]的代价如果染，就会完成所有任务，任何儿子都不参与是最优的。不染的话就全都交给子节点去做，然后由于是虚树，相邻两点的边本质上是一条链，所以我们需要tmp+=min(dp[v],min[a[cur−dep[v]],a[cur−dep[u]−1]])tmp+=min(dp[v],min[a[cur-dep[v]],a[cur-dep[u]-1]])
  • 实现上需要特判叶子的情况，主要是对于tmp的赋初始值
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
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简单路径上只出现一次的边权的权值数量f(u,v)为u到v简单路径上只出现一次的边权的权值数量

参考学习:https://www.luogu.com.cn/article/dad36cgq（待补可撤销并查集以及线段树分治）

Sol：先考虑朴素做法。把所有颜色c的边砍去，答案就是相邻联通块大小乘积。这个是因为如果一条路径进入了大于两个「联通块」，那么就会出现两条颜色为 c的边。但这样枚举边的颜色，再dp统计的时间复杂度不对。

考虑颜色相关的均摊，想到虚树做法。每个值贡献独立，枚举边颜色cur，把边权两端的点全部抽出来建立虚树。

  • sf[i]代表i子树内和i在同个「联通块」的有几个点。sf[i] 代表 i 子树内和 i 在同个「联通块」的有几个点。
  • ot[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 的后面部分是不在虚树上的点的个数的贡献

  • otuot_{u}的前面部分是和它在同个「联通块」的儿子的子树贡献，考虑u和v在同一联通块，则要统计与自己不在一起的联通块大小递归到和儿子不在一起的otvot_{v}。

  • otuot_{u}的后面部分是和它在不同「联通块」的儿子的联通块贡献。考虑u和v不在同一联通块，则要统计与自己不在一起的联通块大小递归到和儿子在一起的sfvsf_{v}。

最后统计答案，应该是每个「联通块」的根(最高点），把自己的「联通块」的大小乘上身边「联通块」的大小总和，形式化地，

res=∑sf_{u}ot_{u}[u=rt \or ⁡w(u,fau)=c]

实现细节：建立虚树的时候需要加边，这关系到在哪里统计答案。需要开set或者map去记录这两点之间存不存在颜色为c的边，因为是虚树，两个点之间可能没什么关系，所以要支持快速随机访问。

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
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;
}