写在前面的
这是我不想做第二次的题目。
分析
我们什么都不说了,直接定义状态 表示 节点是否作为蓝线的中点的最优解。那么我们通过分析,一条蓝边一定是 的路径。所以先考虑 的暴力树形 。 和 ,然后 就写好了。
#include<bits/stdc++.h> int read() {int x;scanf("%d",&x);return x;} using namespace std; const int N = 12010,inf = 0x3f3f3f3f; #define pii pair<int,int> vector<pii> G[N]; int n,f[N][2]; void dfs(int x,int fa) { f[x][0] = 0;int tot = 0; for(auto e : G[x]) { int y = e.first,w = e.second; if(y == fa) continue; dfs(y,x);tot++; f[x][0] += max(f[y][0],f[y][1] + w); } if(!tot) f[x][1] = -inf; if(!tot) return; f[x][1] = -inf; for(auto e : G[x]) { int y = e.first,w = e.second; if(y == fa) continue; f[x][1] = max(f[x][1],f[y][0] + w - max(f[y][0],f[y][1] + w)); } f[x][1] += f[x][0]; } int main() { n = read(); for(int a,b,c,i=1;i<n;i++) { a = read();b = read();c=read(); G[a].push_back(pii(b,c)); G[b].push_back(pii(a,c)); } int ans = 0; for(int i = 1;i <= n;i++) dfs(i,0),ans = max(ans,f[i][0]); cout << ans << endl; }
现在我们考虑如何换根。这里的式子无比恶心,我这里直接放图片吧。 其中 表示这个节点为根的答案。 表示除开这个节点子树的答案。
#include<bits/stdc++.h> int read() {int x;scanf("%d",&x);return x;} using namespace std; const int N = 210000,inf = 0x3f3f3f3f; #define pii pair<int,int> vector<pii> G[N]; int n,f[N][2],son1[N],son2[N],mx1[N],mx2[N]; int g[N][2],k[N][2],val[N]; void dfs(int x,int fa) { f[x][0] = 0;f[x][1] = -inf; mx1[x] = mx2[x] = -inf;son1[x] = son2[x] = 0; for(auto e : G[x]) { int y = e.first,w = e.second; if(y == fa) continue; val[y] = w; dfs(y,x); f[x][0] += max(f[y][0],f[y][1] + w); } for(auto e : G[x]) { int y = e.first,w = e.second; if(y == fa) continue; int val = f[y][0] + w - max(f[y][0],f[y][1] + w); if(val > mx1[x]) {swap(son1[x],son2[x]);swap(mx1[x],mx2[x]);mx1[x]=val;son1[x]=y;} else if(val > mx2[x]) {son2[x]=y;mx2[x]=val;} } f[x][1] = f[x][0] + mx1[x]; } void solve(int x,int fa) { for(auto e : G[x]) { int y = e.first,w = e.second; if(y == fa) continue; if(son1[x] == y) {swap(son1[x],son2[x]);swap(mx1[x],mx2[x]);} k[x][0] = g[x][0] - max(f[y][0],f[y][1] + w); k[x][1] = k[x][0] + mx1[x]; if(fa) {k[x][1] = max(k[x][1],k[x][0] + k[fa][0] + val[x] - max(k[fa][0],k[fa][1]+val[x]));} g[y][0] = f[y][0] + max(k[x][0],k[x][1] + w); if(mx1[x] < mx2[x]) {swap(mx1[x],mx2[x]);swap(son1[x],son2[x]);} solve(y,x); } } int main() { n = read(); for(int a,b,c,i=1;i<n;i++) { a = read();b = read();c=read(); G[a].push_back(pii(b,c)); G[b].push_back(pii(a,c)); } dfs(1,0);g[1][0] = f[1][0]; solve(1,0);int ans = 0; for(int i = 1;i <= n;i++) ans = max(ans,g[i][0]); cout << ans << endl; }