题意：一颗无向树，选两条边不重复的路径，删去选择的点和路径剩下一些cc，求最多cc数。
update 5.1 : 刚刚发现bzoj上这个做法被hack了....以后再想一下别的做法吧
一开始以为这是三合一，写了x=2和x=1. 后来才明白...人家给出的本来就是最优...你自己再求也无所谓
x=0的树形DP没有想出来，感觉很不好处理。
是对边进行树形DP
对于有向边\(p:(u,v)\),\(f(p), g(p), d(p)\)分别表示从v出发走一条，在v子树中走一条经过v，v子树 的最大cc数
注意这个cc数不考虑u所在cc
转移和我一开始想的传统树形DP类似
当时我就卡在了如何更新答案的地方：
- 两条路径不相交，\(d[i]+d[i \oplus 1]\)，或者一个点的两个子树任选+1
- 两条路径交于一点，从这一点走出三条或四条
\(d[i]+d[i \oplus 1]\)这一个转移很巧妙！利用了边是有方向的！
然后我WA了半天结果是被n=1 hack了....
#include#include #include #include using namespace std;typedef long long ll;#define fir first#define sec secondconst int N = 2e5+5;inline int read() { char c=getchar(); int x=0,f=1; while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}int n, u, v;struct edge{int v, ne;} e[N];int cnt=1, h[N];inline void ins(int u, int v) { e[++cnt] = (edge){v, h[u]}; h[u] = cnt; e[++cnt] = (edge){u, h[v]}; h[v] = cnt;}int f[N], g[N], d[N], vis[N], de[N];struct meow{ int a, b, c, d; meow():a(0), b(0), c(0), d(0){}};void dp(int p) { if(vis[p]) return; vis[p] = 1; int u = e[p].v, child = 0; meow t; for(int i=h[u];i;i=e[i].ne) if(i != (p^1)) { child++; dp(i); d[p] = max(d[p], d[i]); if(f[i] >= t.a) t.b = t.a, t.a = f[i]; else if(f[i] > t.b) t.b = f[i]; } f[p] = max(t.a, 1) + child - 1; g[p] = max(t.a, 1) + max(t.b, 1) + child - 2; d[p] = max(d[p], g[p]);}void solve() { int ans = 0; for(int i=2; i<=cnt; i++) dp(i), dp(i^1), ans = max(ans, d[i] + d[i^1]); for(int u=1; u<=n; u++) { meow t; meow r; for(int i=h[u];i;i=e[i].ne) { if(f[i] >= t.a) t.d = t.c, t.c = t.b, t.b = t.a, t.a = f[i]; else { if(f[i] >= t.b) t.d = t.c, t.c = t.b, t.b = f[i]; else { if(f[i] >= t.c) t.d = t.c, t.c = f[i]; else if(f[i] > t.d) t.d = f[i]; } } if(d[i] >= r.a) r.b = r.a, r.a = d[i]; else if(d[i] > r.b) r.b = d[i]; } ans = max(ans, r.a + r.b + 1); ans = max(ans, t.a + t.b + t.c + de[u] - 3); ans = max(ans, t.a + t.b + t.c + t.d + de[u] - 4); } printf("%d\n", ans);}int main() { freopen("in", "r", stdin); int T=read(), x=read(); while(T--) { n=read(); cnt = 1; for(int i=1; i<=n; i++) h[i] = de[i] = 0; if(x==1) read(), read(); if(x==2) read(), read(), read(), read(); for(int i=1; i