2023.08.19：修改了一处笔误。
手玩发现对于一颗生成树，如果存在至少一个点的度数 \(> 2\)（即不为链），那么肯定能使得所有棋子都在一条边的两个端点上。
因为有度数 \(> 2\) 的点的存在，这里就可以合并与其相连的点的棋子。
先考虑非链的情况的答案，记两部分棋子黑白棋子颜色分别为 \(c(a/b)(0/1)\)。
由两部分棋子在一条边上考虑到二分图。
若为二分图，则不管怎么走两部分棋子所在的颜色都是不同的，即两部分棋子最优情况也还是中间有一条边，答案为 \(w_{\max}\times (c(a)(0)\times c(b)(1) + c(a)(1)\times c(b)(0))\)。
若不为二分图，则图上肯定存在奇环，可以利用这个奇环分割开黑白棋子并把黑白棋子分别凑在一起，答案为 \(w_{\max}\times ((c(a)(0) + c(b)(0))\times (c(a)(1) + c(b)(1)))\)。
再来考虑链的情况。
手玩能发现最后棋子的位置需要满足 \(3\) 点：
- 在链上相邻的两个点操作完的距离 \(\le\) 两个点的初始距离，因为发现选取的空节点只存在两点之间或之外的情况，而距离变化分别为 \(-2\) 和不变。
- 在链上相邻的两个点不会在操作中调换顺序，证明与 1 相似。
- 在链上相邻的两个点操作完的距离与两个点的初始距离模 \(2\) 意义下同余，因为链也是个二分图。
考虑 DP，设 \(f_{i, l, r}\) 为到链上第 \(i\) 个点且这个点上有编号为 \([l, r]\) 的棋子的最大权值，不合法的值为 \(-\inf\)。
记 \(\operatorname{count}([l, r], [L, R])\) 为这 \(2\) 个区间的棋子能产生的配对数，\(\operatorname{dis}(x, y)\) 为这两个棋子在链上的距离。
转移分为 \(2\) 部分：
- 从 \(i - 1\) 选的点与 \([l, r]\) 产生贡献，\(f_{i, l, r} = \max\limits_{L = 1}^{l - 1} ([\operatorname{dis}(l - 1, l)\equiv 1\pmod 2]\times (f_{i - 1, L, l - 1} + \operatorname{count}([L, l - 1], [l, r])\times w(i - 1, i)))\)，可以在枚举的时候维护 \(\operatorname{count}\)，单次 \(O(n)\)。
- 从前面的点转移过来，但是不产生贡献，\(f_{i, l, r} = \max\limits_{j = i - \operatorname{dis(l, l - 1)}}^{i - 1}([i - j\equiv \operatorname{dis}(l - 1, l)\pmod 2]\times (\max\limits_{L = 1}^{l - 1} f_{j, L, l - 1}))\)，但这样是 \(O(n^2)\) 的。
发现对于每个 \(j\) 求的就是右端点为 \(l - 1\) 的最大值，可以预处理 \(g_{i, r} = \max\limits_{l = 1}^r f_{i, l, r}\)，转移式便为 \(f_{i, l, r} = \max\limits_{j = i - \operatorname{dis(l, l - 1)}}^{i - 1}([i - j\equiv \operatorname{dis}(l - 1, l)\pmod 2]\times g_{j, l - 1})\)，时间复杂度 \(O(n)\)。
时间复杂度 \(\mathcal{O}(n^4)\)。
#include<bits/stdc++.h>
const int N = 1e2 + 10;
int n, m, k;
std::vector<int> G[N];
int cx[N], cy[N];
int Gx[N * N], Gy[N * N], Gz[N * N];
int deg[N], deg_cnt[N];
int check_Case1() {
for (int i = 1; i <= m; i++) {
deg[Gx[i]]++, deg[Gy[i]]++;
}
for (int i = 1; i <= n; i++) {
deg_cnt[deg[i]]++;
}
return deg_cnt[1] == 2 && deg_cnt[2] == n - 2;
}
int mcol[N];
void dfs(int u, int &flg) {
for (auto v : G[u]) {
if (mcol[v] == -1) {
mcol[v] = mcol[u] ^ 1, dfs(v, flg);
} else {
flg &= mcol[u] != mcol[v];
}
}
}
int check_Case2() {
for (int i = 1; i <= m; i++) {
G[Gx[i]].push_back(Gy[i]), G[Gy[i]].push_back(Gx[i]);
}
memset(mcol, -1, sizeof(int) * (n + 1));
int flg = 1;
mcol[1] = 0, dfs(1, flg);
return flg;
}
int cnt[2][2];
std::pair<int, int> c[N];
std::vector<std::pair<int, int> > Gc[N];
int dep[N], w[N];
int f[N][N][N], g[N][N];
int d[N], rd[N], ld[N];
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= k; i++) {
scanf("%d%d", &cx[i], &cy[i]);
}
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &Gx[i], &Gy[i], &Gz[i]);
}
if (check_Case1()) {
for (int i = 1; i <= m; i++) {
Gc[Gx[i]].emplace_back(Gy[i], Gz[i]), Gc[Gy[i]].emplace_back(Gx[i], Gz[i]);
}
int st = -1, ed = -1;
for (int i = 1; i <= n; deg[i] == 1 && (st == -1 ? st = i : ed = i, 1), i++);
for (int i = st, d = 1; d <= n; d++) {
dep[i] = d;
std::pair<int, int> v = dep[Gc[i][0].first] == 0 ? Gc[i][0] : Gc[i][1];
i = v.first, w[d + 1] = v.second;
}
for (int i = 1; i <= k; i++) {
c[i] = {cx[i], cy[i]};
}
std::sort(c + 1, c + k + 1, [](std::pair<int, int> a, std::pair<int, int> b) {
return dep[a.first] < dep[b.first];
});
for (int i = 1; i < k; i++) {
d[i] = dep[c[i + 1].first] - dep[c[i].first];
}
rd[k] = k;
for (int i = k - 1; i; i--) {
rd[i] = (d[i] & 1) ? i : rd[i + 1];
}
ld[1] = 1;
for (int i = 2; i <= k; i++) {
ld[i] = (d[i - 1] & 1) ? i : ld[i - 1];
}
memset(f, -0x3f, sizeof(f));
memset(g, -0x3f, sizeof(g));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= rd[1]; j++) {
f[i][1][j] = 0, g[i][j] = 0;
}
}
for (int i = 2; i <= n; i++) {
for (int l = 2; l <= k; l++) {
cnt[0][0] = cnt[1][0] = 0;
int R = l - 1;
for (int r = l; r <= rd[l]; r++) {
cnt[c[r].second][0]++;
if (d[R] & 1) {
cnt[0][1] = cnt[1][1] = 0;
for (int L = R; L >= ld[R]; L--) {
cnt[c[L].second][1]++;
f[i][l][r] = std::max(f[i][l][r], f[i - 1][L][R] + w[i] * (cnt[0][0] * cnt[1][1] + cnt[1][0] * cnt[0][1]));
}
}
for (int j = i - d[R] > 0 ? i - d[R] : (((i - d[R]) & 1) ? 1 : 2); j < i; j += 2) {
f[i][l][r] = std::max(f[i][l][r], g[j][R]);
}
g[i][r] = std::max(g[i][r], f[i][l][r]);
}
}
}
int ans = f[0][0][0];
for (int i = 1; i <= n; i++) {
for (int l = ld[k]; l <= k; l++) {
ans = std::max(ans, f[i][l][k]);
}
}
printf("%d\n", ans);
} else if (check_Case2()) {
for (int i = 1; i <= k; i++) {
cnt[cy[i]][mcol[cx[i]]]++;
}
int mxz = 0;
for (int i = 1; i <= m; mxz = std::max(mxz, Gz[i]), i++);
printf("%d\n", mxz * (cnt[0][0] * cnt[1][1] + cnt[0][1] * cnt[1][0]));
} else {
for (int i = 1; i <= k; i++) {
cnt[cy[i]][0]++;
}
int mxz = 0;
for (int i = 1; i <= m; mxz = std::max(mxz, Gz[i]), i++);
printf("%d\n", mxz * (cnt[0][0] * cnt[1][0]));
}
return 0;
}