【HYSBZOJ】【树形DP】3677 [Apio2014]连珠线

HYSBZOJ 3677 [Apio2014]连珠线

题目大意

◇题目传送门◆

BZOJ 上的题面太毒瘤了，我来重写一下

给定$N$个珠子，现在可以进行如下操作：

• Append(w,v)：将一个新的珠子$w$用红线与一个已经添加了的珠子$v$连起来；
• Insert(w,u,v)：将一个新的珠子插入到用红线连起来的珠子$u,v$，即断开$u,v$的红线，并用蓝线连接$w,v$和$w,u$。

给出最后的状态（保证是一棵树），即珠子的连接状态和线的长度，现在要求最大化蓝线的总长度。

分析

考虑最后的状态下蓝线的连接情况，一定是从某个节点的儿子 -> 某个节点 -> 它的父亲。

明显的换根 DP 。

设状态$f(u,0/1)$为当前在节点$u$，其中$0$表示$u$不是蓝线的中点，而$1$表示$u$是蓝线的中点。

考虑$f(u,0)$的转移，对于$f(u,0)$，我们要使它不是中点，我们就要满足对于它的任何一个儿子$v$，它作为中点（$f(v,1)+w_{u,v}$）和它也不是中点（$f(v,0)$）。则我们得出$f(u,0)$的转移：

$$f(u,0)=\sum _{v\in son(u)}\max (f(v,1)+w_{u,v},f(v,0))$$

考虑$f(u,1)$的转移，对于$f(u,1)$，我们可以枚举这条蓝线连接的儿子$v$，其他的点仍然按照$f(u,0)$的方法转移，那么对于$v$，我们必须先减掉它原来的贡献，再加上它现在的贡献$f(v,0)+w_{u,v}$，所以得出$f(u,1)$的状态转移：

f(u,1)=f(u,0)+max?v∈son(u){f(v,0)+wu,v?max?(f(v,0)+wu,v,f(v,1))}f(u,1)=f(u,0)+\max_{v\in son(u)}\left\{f(v,0)+w_{u,v}-\max(f(v,0)+w_{u,v},f(v,1))\right\} f(u,1)=f(u,0)+v∈son(u)max?{ f(v,0)+wu,v??max(f(v,0)+wu,v?,f(v,1))}

这样我们做出了以某个节点为根的状态转移。

考虑换根：一个点的儿子在成为它的父亲之后，原来的儿子的贡献就会消失，这个点的贡献就会加到原来的儿子（现在的父亲）上去。显然必须记录次大值

为了方便地换根，我们另外定义状态$v(u,0/1,j)$表示在计算$u$的$f$值时不考虑第$j$棵子树的代价，另外，为了方便，我们也可以顺带记录下去掉这个子树后的最大值。

考虑换根时的一些细节。注意到一个点$u$换了根后，它的父亲会变成它的儿子（即对$u$产生贡献），所以我们应该先重新计算它的父亲对它的贡献，再来统计答案和换根。

参考代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;const int Maxn = 200000;
const int INF = 0x3f3f3f3f;int N;
vector<pair<int, int> > G[Maxn + 5];
void addedge(int u, int v, int w) {
    G[u].push_back(make_pair(v, w));G[v].push_back(make_pair(u, w));
}int f[2][Maxn + 5];
vector<int> val[2][Maxn + 5], mx_son_val[Maxn + 5];
vector<int> son[Maxn + 5];
int len[Maxn + 5];
void PreDFS(int u, int fa) {
    f[0][u] = 0, f[1][u] = -INF;int mx1 = -INF, mx2 = -INF;for(int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i].first, w = G[u][i].second;if(v == fa) continue;PreDFS(v, u), len[v] = w;son[u].push_back(v);f[0][u] += max(f[0][v], f[1][v] + w);int tmp = f[0][v] + w - max(f[0][v], f[1][v] + w);if(tmp > mx1) mx2 = mx1, mx1 = tmp;else if(tmp > mx2) mx2 = tmp;}f[1][u] = f[0][u] + mx1;for(int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i].first, w = G[u][i].second;if(v == fa) continue;val[0][u].push_back(f[0][u] - max(f[0][v], f[1][v] + w));int tmp = f[0][v] + w - max(f[0][v], f[1][v] + w);if(tmp == mx1) {
    val[1][u].push_back(val[0][u].back() + mx2);mx_son_val[u].push_back(mx2);} else {
    val[1][u].push_back(val[0][u].back() + mx1);mx_son_val[u].push_back(mx1);}}
}
int ans;
void DFS(int u, int fa) {
    for(int i = 0; i < (int)son[u].size(); i++) {
    int v = son[u][i];f[0][u] = val[0][u][i], f[1][u] = val[1][u][i];if(fa != 0) {
    f[0][u] += max(f[0][fa], f[1][fa] + len[u]);f[1][u] = f[0][u] + max(mx_son_val[u][i], f[0][fa] + len[u] - max(f[0][fa], f[1][fa] + len[u]));}ans = max(ans, f[0][v] + max(f[0][u], f[1][u] + len[v]));DFS(v, u);}
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d", &N);for(int i = 1; i < N; i++) {
    int u, v, w;scanf("%d %d %d", &u, &v, &w);addedge(u, v, w);}PreDFS(1, 0);DFS(1, 0);printf("%d\n", ans);return 0;
}
//f[u][0/1]:
//f[u][0] = sum(max(f[v][0], f[v][1] + w(u, v)))
//f[u][1] = f[u][0] + max(f[v][0] + w(u, v) - max(f[v][0], f[v][1] + w(u, v)))