记录编号	492445	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HEOI 2017] 摧毁“树状图”	最终得分	100
用户昵称	Furyton	是否通过	通过
代码语言	C++	运行时间	2.921 s
提交时间	2018-03-26 07:30:38	内存使用	3.14 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define File(x) "treediagram."#x
#define For(i,s,e) for(int i=(s); i<=(e); i++)
#define Rep(i,s,e) for(int i=(s); i>=(e); i--)
#define Max(a, b) a=(a>b?a:b)
using namespace std;
typedef long long LL;
const int N=100000+1;
struct Node{
	int x,nxt;
}T[N];

priority_queue<int>F;
int n, Q, h[N], len, x, p0, u, v;
int f[N][2], g[N][2][2], son[N];

void addEdge(int x, int y){
	T[++len]=(Node){y, h[x]}; h[x]=len;
}

void dfs(int,int);

int main()
{
	freopen(File(in),"r",stdin);
	freopen(File(out),"w",stdout);

	scanf("%d%d",&Q,&x);
	while(Q--){
		memset(h,0,sizeof(h)); len=0;

		scanf("%d",&n);
		if(x==1) For(i,1,2) scanf("%d",&p0);
		if(x==2) For(i,1,4) scanf("%d",&p0);

		For(i,1,n-1){
			scanf("%d%d",&u,&v);
			addEdge(u, v); addEdge(v, u);
		}
		dfs(1,0);

		printf("%d\n",max(son[1]?g[1][1][0]+1:0, g[1][1][1]));
	}

    return 0;
}
void dfs(int x, int fa){
	son[x]=0; f[x][0]=f[x][1]=g[x][0][0]=g[x][0][1]=g[x][1][0]=g[x][1][1]=0;
	for(int p=h[x]; p; p=T[p].nxt){
		if(T[p].x==fa) continue;
		dfs(T[p].x, x); son[x]++;
	}

	while(!F.empty()) F.pop();
	for(int p=h[x]; p; p=T[p].nxt){
		if(T[p].x==fa) continue;
		int s=T[p].x, s2;

		F.push(f[s][0]);
		Max(f[x][0], son[x]); Max(f[x][0], f[s][0]+son[x]-1);

		Max(f[x][1], g[s][0][0]+son[x]); Max(f[x][1], g[s][0][1]+son[x]-1);
		Max(f[x][1], f[s][1]+son[x]-1);
		Max(f[x][1], f[s][0]+son[x]-1); Max(f[x][1], son[x]);

		Max(g[x][0][0], g[s][0][0]); Max(g[x][0][0], g[s][0][1]);
		Max(g[x][0][1], son[x]); Max(g[x][0][1], f[s][0]+son[x]-1);

		Max(g[x][1][0], g[s][1][0]); Max(g[x][1][0], g[s][1][1]);
		Max(g[x][1][0], g[s][0][0]); Max(g[x][1][0], g[s][0][1]);

		Max(g[x][1][1], g[s][0][1]+son[x]-1); Max(g[x][1][1], g[s][0][0]+son[x]);
		Max(g[x][1][1], f[s][1]+son[x]-1); 
		Max(g[x][1][1], son[x]); //Max(g[x][1][1], g[s][1][1]);

		for(int p2=h[x]; p2; p2=T[p2].nxt){
			if(T[p2].x==fa || T[p2].x==s) continue;
			s2=T[p2].x;
			Max(f[x][1], f[s][0]+g[s2][0][0]+son[x]-1);
			Max(f[x][1], f[s][0]+g[s2][0][1]+son[x]-2);

			Max(g[x][0][1], f[s][0]+f[s2][0]+son[x]-2);

			Max(g[x][1][0], max(g[s][0][0], g[s][0][1])+max(g[s2][0][0], g[s2][0][1]));
			Max(g[x][1][1], f[s][0]+f[s2][0]+son[x]-2);
			Max(g[x][1][1], f[s][0]+f[s2][1]+son[x]-2);
			Max(g[x][1][1], f[s][0]+g[s2][0][0]+son[x]-1);
			Max(g[x][1][1], f[s][0]+g[s2][0][1]+son[x]-2); 

			for(int p3=h[x]; p3; p3=T[p3].nxt){
				if(T[p3].x==fa || T[p3].x==s || T[p3].x==s2) continue;
				int s3=T[p3].x;
				Max(g[x][1][1], f[s][0]+f[s2][0]+g[s3][0][1]+son[x]-3);
				Max(g[x][1][1], f[s][0]+f[s2][0]+g[s3][0][0]+son[x]-2);
			}
		}
	}
	if(!F.empty()){
		int tmp3=son[x]-3, tmp4=son[x]-4;
		if(son[x]>=3){
			For(i,1,3){
				tmp3+=F.top(); tmp4+=F.top(); F.pop();
			}
			if(son[x]>=4){
				tmp4+=F.top();
			}
			Max(f[x][1], tmp3); Max(g[x][1][1], tmp3); Max(g[x][1][1], tmp4);
		}
	}
}