4871: [Shoi2017]摧毁“树状图”

题意：一颗无向树，选两条边不重复的路径，删去选择的点和路径剩下一些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类似

当时我就卡在了如何更新答案的地方：

1. 两条路径不相交，\(d[i]+d[i \oplus 1]\)，或者一个点的两个子树任选+1
2. 两条路径交于一点，从这一点走出三条或四条

\(d[i]+d[i \oplus 1]\)这一个转移很巧妙！利用了边是有方向的！

然后我WA了半天结果是被n=1 hack了....

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

#define fir first

#define sec second

const 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<n; i++) u=read(), v=read(), ins(u, v), de[u]++, de[v]++;

		for(int i=1; i<=cnt; i++) vis[i] = 0, f[i] = g[i] = d[i] = 0;

		if(n == 1) {puts("0"); continue;}

		solve();

	}

	return 0;

}