===
Index
模板
template <class T, // dp值的类型，如ll，int等。
T(*op)(T, T), // 合并运算，需要满足交换律 op(dp[i], dp[j])
T(*e)(), // op 运算单位元，op(x, e()) = x
T(*G)(T, int, int), // 根节点累积信息 G(dp[child], child, fa)
class E, // 边上 weight 的类型
T(*F)(T, int, int, E)> // 子节点信息转移为父节点 F(dp[child], child, fa, weight(child, fa))
struct ReRooting : public vector<vector<pair<int, E>>> {
using base_type = vector<vector<pair<int, E>>>;
public:
static constexpr int NIL = -1;
using base_type::base_type;
void add_edge(int u, int v, const E& w) {
(*this)[u].emplace_back(v, w);
(*this)[v].emplace_back(u, w);
}
const vector<T>& get(int root = 0) {
const int n = this->size();
dp.resize(n), to_par.resize(n);
dfs_subtree(root, NIL);
dfs(root, NIL, e());
return dp;
}
private:
vector<T> dp, to_par;
void dfs_subtree(int u, int p) {
dp[u] = e();
for (auto [v, w] : (*this)[u]) {
if (v == p) continue;
dfs_subtree(v, u);
dp[u] = op(dp[u], to_par[v] = F(G(dp[v], v, u), v, u, w));
}
}
void dfs(int u, int p, T from_p) {
dp[u] = G(dp[u], u, NIL);
const int sz = (*this)[u].size();
vector<T> cum_l { e() };
cum_l.reserve(sz + 1);
for (const auto& [v, _] : (*this)[u]) cum_l.push_back(op(cum_l.back(), v == p ? from_p : to_par[v]));
T cum_r = e();
for (int i = sz - 1; i >= 0; --i) {
const auto& [v, w] = (*this)[u][i];
if (v == p) {
cum_r = op(from_p, cum_r);
} else {
T from_u = F(G(op(cum_l[i], cum_r), u, v), u, v, w);
dp[v] = op(dp[v], from_u);
dfs(v, u, from_u);
cum_r = op(to_par[v], cum_r);
}
}
}
};
// dp[v]=g( op(f(dp[c1], v1), f(dp[c2], v2) , ... f(dp[c2], v2)), v)
using S = int;
using E = nullptr_t;
S op(S x, S y) {
return x * y;
}
S e() {
return 0;
}
S G(S x, int u, int fa) {
return x;
}
S F(S x, int u, int fa, E w) {
return x + 1;
}
// ReRooting<S, op, e, G, E, F> g(n);
简介
考虑以顶点v为根时的树DP。
设 T 是某种数据类型构成的集合。
dp[v] in T dp[v] 表示以v为根的子树的某种数量/判定等。
此时，树DP的迁移
- 两个变量的函数 f,g T * N -> T
- 可交换的 merge T * T -> T
- v 的子集和 ch(v)
使用
dp[v] = g( merge( f(dp[c1], v1), f(dp[c2], v2) , ... f(dp[c2], v2) ) , v)
如果转移能通过这种方式表示，就能够使用换根dp的模板, f 和 g 需要一个顶点编号作为其第二个参数，很多时候是用不到的，merge 必须满足可交换。
其中F 和 G 函数生效位置所对应的dfs中位置如下。
function<void(int, int)> dfs = [&](int u, int fa) {
for(int v : g[u]) if (v != fa) {
dfs(v, u);
F(dp[v], v, u, w);
}
G(dp[u], u, fa);
};
不带边权例题
这类题目中，权值出现在点上，直接设置 using E = nullptr_t;
dp_contest_subtree
n 棵节点的树，编号1-n, 需要将每个节点染成黑色或白色，使得任意黑色节点可以仅经过黑的节点到达其他所有黑色节点。对于每个节点v， 假设v节点必须被染成黑色，求其他节点的染色方案数目，模m。
- 1 <= n <= 1e5
- 2 <= m <= 1e9
分析
dp[i] 表示以节点i为根的子树，在i节点必须染成黑色的情况下的方案数，则
dp[i] = (dp[c1]+1)*(dp[c2]+1)*...(dp[ck]+1) 其中每个子节点要么染成黑色，方案数为dp[ci],要么没有节点染成黑色，方案数为1.
则
- f(a, v) = a + 1
- op(x, y) = x * y
- g(a, v) = a
#include <bits/stdc++.h>
using namespace std;
// rerooting dp
// dynamic_mod
using mint = dynamic_mod<998244353>;
using S = mint;
using E = nullptr_t;
S op(S x, S y) {
return x * y;
}
S e() {
return 1;
}
S G(S x, int u, int fa) {
return x;
}
S F(S x, int u, int fa, E w) {
return x + 1;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
mint::set_mod(m);
ReRooting<mint, op, e, G, E, F> g(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
std::cin >> x >> y;
--x, --y;
g.add_edge(x, y, nullptr);
}
for (mint e : g.get()) {
std::cout << e.val() << '\n';
}
return 0;
}
最多白色节点子树
n 棵节点的树，编号1-n, 给定长度为n数组a，a[i]=1 表示节点i是白色，0为黑色，对于每个节点v，求：选择一个包含v节点的子树，该子树的白色节点数与黑色节点数的差最大。
- 2 <= n <= 2e5
- a[i] = 0 或 1
分析
dp[v]表示表示以v为根的子树，必须选择v时，白色节点数与黑色节点数的最大差。
则 dp[v] = max(dp[c1],0)+max(dp[c2],0)+...+ max(dp[ck],0) + w[v] a[v]=1时，w[v]=1, 否则为-1.
vector<int> a;
using S = int;
using E = nullptr_t;
S op(S x, S y) {
return x + y;
}
S e() {
return 0;
}
S G(S x, int u, int fa) {
return x + a[u];
}
S F(S x, int u, int fa, E w) {
return max(x, 0);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
a.resize(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (a[i] == 0) a[i] = -1;
}
ReRooting<S, op, e, G, E, F> g(n);
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
u--, v--;
g.add_edge(u, v, nullptr);
}
for (auto &p : g.get()) {
cout << p << ' ';
}
cout << '\n';
return 0;
}
去掉一个端点的最长路径和
一个 n 个节点的无向无根图, 每个节点有一个价值，p[i] 表示第 i 个节点的价值。 一条路径的 价值和 是这条路径上所有节点的价值之和。
求从任意节点出发的价值最大的路径与价值最小的路径的差值的最大值。
- 1 <= n <= 1e5
- 1 <= p[i] <= 1e5
分析
由于所有的 价值 都是正数，因此以 root 为端点的最短路径只能包含一个节点，也就是 root 本身。另外路径需要以 root 为端点，因此根为u时的最优解是 从u出发，不包括u的最长路径和. dp 转移为
dp[u] = max( dp[c1] + p[c1], dp[c2]+p[c2] + ... + dp[ck]+p[ck] )
using S = long long;
using E = nullptr_t;
vector<int> p;
S op(S x, S y) {
return x > y ? x : y;
}
S e() {
return 0;
}
S G(S x, int u, int fa) {
return x;
}
S F(S x, int u, int fa, E w) {
return x + p[u];
}
long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {
ReRooting<S, op, e, G, E, F> g(n);
p = price;
for (auto& e : edges) {
int u = e[0], v = e[1];
g.add_edge(u, v, nullptr);
}
auto a = g.get();
long long ans = 0;
for (int i = 0; i < n; ++i){
ans = std::max(ans, a[i]);
}
return ans;
}
树中距离之和
给定一个无向、连通的树。树中有 n 个标记为 0…n-1 的节点以及 n-1 条边 。
给定整数 n 和数组 edges ， edges[i] = [ai, bi]表示树中的节点 ai 和 bi 之间有一条边。
返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。
分析
dp[u]: 树中第 u 个节点与所有其他节点之间的距离之和，则转移为：
dp[u] = ∑(dp[v] + siz[v]) 其中， dp[u] 和 siz[u] 均需要通过dp求得，所以可以定义S为 pair。
其中 siz[u] = ∑(siz[v]) + 1 .
using S = pair<long long, int>;
using E = nullptr_t;
S op(S x, S y) {
return S{x.first + y.first, x.second + y.second};
}
S e() {
return S{};
}
S G(S x, int u, int fa) {
return S{x.first, x.second + 1};
}
S F(S x, int u, int fa, E w) {
return S{x.first + x.second, x.second};
}
// ReRooting<S, op, e, G, E, F> g(n);
vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
ReRooting<S, op, e, G, E, F> g(n);
for (auto &e : edges) {
int u = e[0], v = e[1];
g.add_edge(u, v, nullptr);
}
vector<int> ans;
for (auto x : g.get()) {
ans.push_back(x.first);
}
return ans;
}
最大深度和
给定一个 n 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。一个结点的深度定义为该节点到根的简单路径上边的数量。
分析
和上题一样的转移公式
using S = pair<long long, int>;
using E = nullptr_t;
S op(S x, S y) {
return S{x.first + y.first, x.second + y.second};
}
S e() {
return S{};
}
S G(S x, int u, int fa) {
return S{x.first, x.second + 1};
}
S F(S x, int u, int fa, E w) {
return S{x.first + x.second, x.second};
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
ReRooting<S, op, e, G, E, F> g(n);
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
u--, v--;
g.add_edge(u, v, nullptr);
}
long long ans = 0;
int id = 0, cur = 0;;
for (auto &[k, v] : g.get()) {
if (k > ans) {
ans = k, id = cur;
}
cur++;
}
cout << id + 1 << '\n';
return 0;
}
可以到达每一个节点的最少边翻转次数
给定一个n个节点的简单有向图，如果这些边是双向边，则形成一棵树。 边反转 指的是将一条边的方向反转，也就是说一条从节点 ui 到节点 vi 的边会变为一条从节点 vi 到节点 ui 的边。 对于每一个节点i,独立计算 最少 需要多少次 边反转 ，从节点 i 出发经过一系列有向边 ，可以到达所有的节点。
- 2 <= n <= 1e5
换根dp
对于节点i，需要翻转的边数等于以节点i为根时，到达所有其它节点路径上反向边的总数。可以使用换根dp.
dp[v] = (dp[c1] + (v, c1) not in es) + ... + (dp[ck] + (v, ck) not in es)
using S = int;
using E = nullptr_t;
set<pair<int,int>> s;
S op(S x, S y) {
return x + y;
}
S e() {
return 0;
}
S G(S x, int u, int fa) {
return x + s.count({u, fa});
}
S F(S x, int u, int fa, E w) {
return x;
}
class Solution {
public:
vector<int> minEdgeReversals(int n, vector<vector<int>>& es) {
s.clear();
ReRooting<S, op, e, G, E, F> g(n);
for (auto &e : es) {
int u = e[0], v = e[1];
g.add_edge(u, v, nullptr);
s.emplace(u, v);
}
return g.get();
}
};
dfs序树上差分
考虑一条边对于哪些点是需要反转的。我们发现是其出发节点对应的一整个联通部分。我们要是有方法对这些位置全部 +1，那么我们直接枚举每一条边就可以得到要的答案了。
事实上这也是可以做到的。我们按照 DFS 序遍历整棵树（可以随意选根）。则每个点对应的子树都是这个序列的一个区间。而我们要更新的，要么是子树，要么是除去子树的所有节点，而这也必然对应着区间。因此可以这样实现更新。更新区间只需要使用差分数组即可。
vector<int> minEdgeReversals(int n, vector<vector<int>>& es) {
vector<vector<int>> g(n);
for (auto & e : es) {
int u = e[0], v = e[1];
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> in(n), out(n), pa(n, -1);
int t = 0;
function<void(int, int)> dfs = [&](int u, int fa) {
pa[u] = fa, in[u] = t++;
for (int v : g[u]) if (v != fa) {
dfs(v, u);
}
out[u] = t;
};
dfs(0, -1);
vector<int> d(n + 1);
auto add = [&](int l, int r) {
d[l]++, d[r]--;
};
for (auto & e : es) {
int u = e[0], v = e[1];
if (pa[v] == u) {
add(in[v], out[v]);
} else {
add(0, in[u]);
add(out[u], n);
}
}
for (int i = 0; i < n; ++i)
d[i + 1] += d[i];
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[i] = d[in[i]];
}
return ans;
}
统计可能的树根数目
n个节点的树，长为m的二维数组q，每个数组表示为[u,v]，表示u是v的父节点。 求有多少个节点i，当以i为根时，q中至少有k项是对的。
- 2 <= n <= 1e5
- 1 <= m <= n - 1
换根
using S = int;
using E = nullptr_t;
set<pair<int,int>> s;
S op(S x, S y) {
return x + y;
}
S e() {
return 0;
}
S G(S x, int u, int fa) {
return x + s.count({fa, u});
}
S F(S x, int u, int fa, E w) {
return x;
}
class Solution {
public:
int rootCount(vector<vector<int>>& es, vector<vector<int>>& guesses, int k) {
s.clear();
int n = es.size() + 1;
ReRooting<S, op, e, G, E, F> g(n);
for (auto &e : es) {
int u = e[0], v = e[1];
g.add_edge(u, v, nullptr);
}
for (auto &e : guesses) {
int u = e[0], v = e[1];
s.emplace(u, v);
}
auto d = g.get();
int c = 0;
for (int i = 0; i < n; ++i) {
if (d[i] >= k) c ++;
}
return c;
}
};
dfs序树上差分
class Solution {
public:
int rootCount(vector<vector<int>>& es, vector<vector<int>>& guesses, int k) {
int n = es.size() + 1;
vector<vector<int>> g(n);
for (auto & e : es) {
int u = e[0], v = e[1];
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> in(n), out(n), dep(n, -1);
int t = 0;
function<void(int, int)> dfs = [&](int u, int fa) {
in[u] = t++;
dep[u] = fa < 0 ? 0 : dep[fa] + 1;
for (int v : g[u]) if (v != fa) {
dfs(v, u);
}
out[u] = t;
};
dfs(0, -1);
vector<int> d(n + 1);
auto add = [&](int l, int r) {
d[l]++, d[r]--;
};
for (auto & e : guesses) {
int u = e[0], v = e[1];
if (dep[u] < dep[v]) {
add(0, in[v]);
add(out[v], n);
} else {
add(in[u], out[u]);
}
}
for (int i = 0; i < n; ++i)
d[i + 1] += d[i];
int ans = 0;
for (int i = 0; i < n; ++i) if (d[i] >= k) ans++;
return ans;
}
};
树异或
一棵n个节点的树，每个节点有个值a[i], 你的目的是通过如下操作将所有a[i]变得相等。 每次操作可以选择任意节点v和任意整数c，然后对v子树中所有顶点，将a[i]替换为 a[i]^c. 操作的代价为v子树中节点数目与c的乘积。设以i为根节点时的最小代价为mi，求m1,m2,..mn的最小值。
- 1 <= n <= 2e5
- 0 <= a[i] < 2^20
分析
以i为根时，i的所有子节点都要先变为a[i],再向父节点操作。
vector<int> a;
using S = pair<long long, int>;
using E = nullptr_t;
S op(S x, S y) {
return S{x.first + y.first, x.second + y.second};
}
S e() {
return S{};
}
S G(S x, int u, int fa) {
return S{x.first, x.second + 1};
}
S F(S x, int u, int fa, E w) {
return S{(a[u]^a[fa])*1ll*(x.second)+x.first, x.second};
}
void ac_yyf(int tt) {
cin >> n;
a.resize(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
ReRooting<S, op, e, G, E, F> g(n);
for (int i = 1, u, v, w; i < n; ++i) {
cin >> u >> v;
u--, v--;
g.add_edge(u, v, nullptr);
}
auto p=g.get();
f0(n)dbg(p[i].first);wt(nl);
}
边权例题
树上边权加终点点权最长路径
输入 n(2≤n≤2e5) 和一棵树的 n-1 条边（节点编号从 1 开始），每条边输入两个端点和边权。 然后输入 n 个数 d，d[i] 表示点 i 的点权。
定义 f(x,y) = 从 x 到 y 的简单路径的边权之和，再加上 d[y]。 定义 g(x) = max{f(x,i)}，这里 i 取遍 1~n 的所有不为 x 的点。 输出 g(1),g(2),…,g(n)。
分析
dp[v]表示表示以v为根的子树的最长路径，则
dp[v] = max( max(dp[c1], d[c1]) + w(c1,v), ... max(dp[ck], d[ck]) + w(ck,v), )
using S = long long;
using E = int;
vector<int> d;
S op(S x, S y) {
return x > y ? x : y;
}
S e() {
return 0;
}
S G(S x, int u, int fa) {
return x;
}
S F(S x, int u, int fa, E w) {
return op(x, d[u]) + w;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
ReRooting<S, op, e, G, E, F> g(n);
for (int i = 1, u, v, w; i < n; ++i) {
cin >> u >> v >> w;
u--, v--;
g.add_edge(u, v, w);
}
d.resize(n);
for (int i = 0; i < n; ++i) {
cin >> d[i];
}
auto a = g.get();
for (int i = 0; i < n; ++i) {
cout << a[i] << "\n";
}
return 0;
}
最小神秘值
输入 n(2≤n≤2e5) 和一棵树的 n-1 条边（节点编号从 1 开始），每条边输入两个端点和边权。 定义节点u,v之间的代价为 u,v路径上的边权和 * (dist(u, v) % 3). 每个点的神秘值定义为该点到其它所有节点的代价之和，求树上神秘值最小的节点的神秘值是多少。
- 3 <= N <= 1e6
- 1 <= w[i] <= 1e6
// ReRooting
using S = pair<array<long long, 3>, array<int, 3>>;
using E = int;
S op(S x, S y) {
S s{};
for(int i = 0; i < 3; ++i) {
s.first[i] = x.first[i] + y.first[i];
s.second[i] = x.second[i] + y.second[i];
}
return s;
}
S e() {
return {};
}
S G(S x, int u, int fa) {
x.second[0]++;
return x;
}
S F(S x, int u, int fa, E w) {
S s{};
for (int i = 0, j = 2; i < 3; ++i, j = (j + 1) % 3) {
s.first[i] += w * 1ll * x.second[j] + x.first[j];
s.second[i] += x.second[j];
}
return s;
}
long long min_mystic(vector<vector<int>> &es){
int n=sz(es)+1;
ReRooting<S, op, e, G, E, F> g(n);
for(auto&e:es){
g.add_edge(e[0],e[1],e[2]);
}
auto d=g.get();
ll c=1e18;
for(auto&[f,s]:d){
cmn(c,f[1]+f[2]*2);
}
return c;
}
