Contest0117

发表于

Contest0117 (SHOI2017)

还好没生在上海。。。

T1 摧毁树状图

题面太长不放了，大意是一颗树，删除其中最多有一个交点的两条链，得到的最多联通块

非常暴躁的树形DP

暴躁的状态

以1为树根，讨论每个节点所有形态：

  • 情况A ： x点的子树中，有一条链
    • A-0:该链不经过x
    • A-1:该链经过x，并且x是端点
    • A-2:该链经过x，并且x不是端点
  • 情况B ：x点的子树中，有两条链
    • B-0:两条链都不经过x
    • B-1:x在链上，并且有链可以从x往上延伸
    • B-2:x在链上，并且没有链可以往上延伸

暴躁的转移

设状态为$f[x][i][j]$

还是看代码吧。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<stdio.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
using namespace std;
const int N=100005;
inline int _R(){
	int d=0;char t=getchar();
	while(!isdigit(t))t=getchar();
	for(;isdigit(t);t=getchar())d=(d<<3)+(d<<1)+t-'0';
	return d;
}

int Tote,Last[N],Next[N<<1],End[N<<1];
void Ins(int x,int y){
	End[++Tote]=y;
	Next[Tote]=Last[x];
	Last[x]=Tote;
}

int f[N][2][3];
void DP(int x,int fa){
	int i,u,t=0,tot=0;
	int A0,A1,A2,B0,B1,B2;
	int a0,a1,a2,b0,b1,b2;
	for(i=Last[x];i;i=Next[i]){
		u=End[i];
		if(u==fa)continue;
		DP(u,x);
		
		A0=A1=A2=B0=B1=B2=0;
		a0=f[u][0][0],a1=f[u][0][1],a2=f[u][0][2];
		b0=f[u][1][0],b1=f[u][1][1],b2=f[u][1][2];

		A0=max(a0,max(a1,a2)+1);
		A1=a1+tot;
		A2=f[x][0][1]+a1;

		B0=max(b0,max(b1,b2)+1);
		B0=max(B0,f[x][0][0]+a0-1);
		B0=max(B0,max(f[x][0][0]+a1,f[x][0][0]+a2));
		B1=max(B1,max(f[x][0][2]+a1,f[x][0][1]+a2));
		B1=max(B1,max(f[x][0][1]+a0,tot+b1));
		B1=max(B1,a1+t);
		B2=max(max(f[x][0][2]+a2,f[x][0][2]+a0),max(f[x][0][1]+b1,f[x][1][1]+a1));

		t=max(t+1,tot+max(a0,max(a1,a2)));
		tot++;
		f[x][0][0]=max(f[x][0][0],A0);
		f[x][0][1]=max(f[x][0][1]+1,max(tot,A1));
		f[x][0][2]=max(f[x][0][2]+1,A2);
		f[x][1][0]=max(f[x][1][0],B0);
		f[x][1][1]=max(f[x][1][1]+1,B1);
		f[x][1][2]=max(f[x][1][2]+1,B2);
	}
}
int T,P,n;
int main(){
	freopen("treediagram.in","r",stdin);
	freopen("treediagram.out","w",stdout);
	int i,j,k,x,y;
	T=_R(),P=_R();
	while(T--){
		n=_R();
		for(i=1;i<=P;i++)_R(),_R();
		for(i=1;i<n;i++){
			x=_R(),y=_R();
			Ins(x,y),Ins(y,x);
		}
		DP(1,0);
		printf("%d\n",max(f[1][1][0],max(f[1][1][1],f[1][1][2])));
		//Init
		Tote=0;
		for(i=1;i<=n;i++){
			Last[i]=0;
			for(j=0;j<2;j++)
				for(k=0;k<3;k++)
					f[i][j][k]=0;
		}
	}
}