六省联考2017 摧毁“树状图”

wjh15101051's space

卧薪尝胆，厚积薄发。

六省联考2017 摧毁“树状图”

Date: Mon Apr 01 20:09:40 CST 2019

In Category: NoCategory

Description：

给一棵树，在树上选两条边不相交路径使得剩下的连通块数最多。

$1\leqslant \sum n\leqslant 500000$

Solution：

树形 $DP$ ：

$1$ 、子树为空，连通块数只能为 $1$ 。

$2$ 、子树内有一条链：

$2.1$ 、链与根不相交，即根为空，设为 $a$

$2.2$ 、链与根相交，可以向上延伸，设为 $b$ 。

$2.3$ 、链与根相交，但是链跨过根不能向上延伸，设为 $c$ 。

$3$ 、子树内有两条链：

$3.1$ 、两个都与根不相交，设为 $d$ 。

$3.2$ 、其中一个与根相交可以向上延伸，另一个不过根，设为 $g_1$ 。

$3.3$ 、其中一个与根相交可以向上延伸，另一个过根，设为 $g_2$ 。

$3.4$ 、其中有一个跨过根不能向上延伸，另一个不过根，设为 $f_1$ 。

$3.5$ 、其中有一个跨过根不能向上延伸，另一个过根，设为 $f_2$ 。

在转移的时候维护前面的所有子树的个数，前面所有子树有一个中有链的最大连通块数，前面所有子树有一个是 $2.2$ 的最大连通块数就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 500010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int a[MAXN],b[MAXN],c[MAXN],d[MAXN],g1[MAXN],g2[MAXN],f1[MAXN],f2[MAXN];

#define F 0x3f3f3f3f

#define N (-F)

void dp(int k,int fa)

{

	a[k] = N;b[k] = 0;c[k] = 0;d[k] = N;g1[k] = N;g2[k] = 0;f1[k] = N;f2[k] = 0;

	int totch = 0,maxexi = 0,maxonechain = 0,maxtwochain = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		int v = e[i].to;

		if(v == fa)continue;

		dp(v,k);

		int ak = a[k],bk = b[k],ck = c[k],dk = d[k],g1k = g1[k],g2k = g2[k],f1k = f1[k],f2k = f2[k];

		int val = max(a[v],max(b[v],c[v]));

		a[k] = max(a[k],a[v]);

		a[k] = max(a[k],b[v] + 1);

		a[k] = max(a[k],c[v] + 1);

		++b[k];

		b[k] = max(b[k],b[v] + totch);

		++c[k];

		c[k] = max(c[k],b[v] + maxonechain);

		d[k] = max(d[k],ak + a[v] - 1);

		d[k] = max(d[k],ak + b[v]);

		d[k] = max(d[k],ak + c[v]);

		d[k] = max(d[k],d[v]);

		d[k] = max(d[k],max(g1[v],g2[v]) + 1);

		d[k] = max(d[k],max(f1[v],f2[v]) + 1);

		++g1[k];

		g1[k] = max(g1[k],bk + val);

		g1[k] = max(g1[k],maxexi + b[v]);

		g1[k] = max(g1[k],max(g1[v],g2[v]) + totch);

		++g2[k];

		g2[k] = max(g2[k],ck + b[v]);

		++f1[k];

		f1[k] = max(f1[k],ck + val);

		f1[k] = max(f1[k],b[v] + maxtwochain);

		f1[k] = max(f1[k],maxonechain + max(g1[v],g2[v]));

		++f2[k];

		f2[k] = max(f2[k],g2k + b[v]);

		maxtwochain = max(maxtwochain + 1,max(totch + max(g1[v],g2[v]),max(maxonechain + val,maxexi + b[v])));

		maxonechain = max(maxonechain + 1,totch + b[v]);

		maxexi = max(maxexi + 1,totch + val);

		++totch;

	}

	return;

}

int tp;

void work()

{

	n = rd(); 

	if(tp >= 1)rd(),rd();

	if(tp == 2)rd(),rd();

	for(int i = 1;i < n;++i)add(rd(),rd());

	dp(1,0);

	printf("%d\n",max(d[1],max(max(g1[1],g2[1]),max(f1[1],f2[1]))));

	edgenum = 0;

	for(int i = 1;i <= n;++i)lin[i] = 0;

	return;

}

int main()

{

	int testcases = rd();tp = rd();

	while(testcases--)work();

	return 0;

}

In tag: DP-树形DP

wjh15101051