记录编号	130493	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2012] 道路染色	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2014-10-22 15:44:46	内存使用	14.56 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=320,INF=0x7fffffff/2;
class KM_Solver{
public:
	//求最大匹配
	int N,m,n;//左m右n,一共是N
	//1~m是左半边,m+1~N是右半边
	int (*c)[SIZEN];//c[SIZEN][SIZEN],切记保持第二维的长度
	int slack[SIZEN];
	bool visit[SIZEN];
	int match[SIZEN];
	int label[SIZEN];
	void assign(int a,int b,int A[SIZEN][SIZEN]){m=a,n=b,N=a+b;c=A;}
	bool findpath(int u){
		visit[u]=true;
		for(int i=m+1;i<=N;i++){
			if(visit[i]||c[u][i]==-INF) continue;
			int t=label[u]+label[i]-c[u][i];
			if(!t){
				visit[i]=true;
				if(match[i]==-1||findpath(match[i])){
					match[i]=u;
					return true;
				}
			}
			else if(slack[i]>t) slack[i]=t;
		}
		return false;
	}
	int calc(int a,int b,int A[SIZEN][SIZEN]){
		assign(a,b,A);
		memset(match,-1,sizeof(match[0])*(N+1));
		for(int i=1;i<=m;i++){
			label[i]=-INF;
			for(int j=m+1;j<=N;j++) label[i]=max(label[i],c[i][j]);
		}
		for(int i=m+1;i<=N;i++) label[i]=0;
		for(int i=1;i<=m;i++){
			while(true){
				memset(visit,0,sizeof(visit[0])*(N+1));
				for(int j=m+1;j<=N;j++) slack[j]=INF;
				if(findpath(i)) break;
				int d=INF;
				for(int j=m+1;j<=N;j++) if(!visit[j]) d=min(d,slack[j]);
				for(int j=1;j<=m;j++) if(visit[j]) label[j]-=d;
				for(int j=m+1;j<=N;j++) if(visit[j]) label[j]+=d;
			}
		}
		int ans=0;
		for(int i=m+1;i<=N;i++){
			if(match[i]!=-1) ans+=c[match[i]][i];
		}
		return ans;
	}
}S;
int N;
vector<int> c[SIZEN];
vector<int> son[SIZEN];
int father[SIZEN]={0};
bool vis[SIZEN][SIZEN]={0};
int f[SIZEN][SIZEN];
int A[SIZEN][SIZEN]={0};
int a[SIZEN]={0};
void DFS(int x){
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i];
		if(u==father[x]) continue;
		son[x].push_back(u);
		father[u]=x;DFS(u);
	}
	int deg=son[x].size();
	if(!deg) return;
	for(int i=1;i<=deg;i++){
		int u=son[x][i-1];
		for(int j=1;j<N;j++){
			if(f[u][j]!=INF) A[i][deg+j]=-(f[u][j]+j);
			else A[i][deg+j]=-INF;
		}
	}
	int tmp=-S.calc(deg,N-1,A);
	if(!father[x]){
		f[x][0]=tmp;
		return;
	}
	for(int i=1;i<N;i++){
		if(S.match[deg+i]==-1) f[x][i]=tmp,vis[x][i]=true;
	}
	for(int i=1;i<N;i++){
		if(vis[x][i]) continue;
		vis[x][i]=true;
		//计算f[x][i],即i不能选
		for(int j=1;j<=deg;j++) a[j]=A[j][deg+i],A[j][deg+i]=-INF;
		f[x][i]=-S.calc(deg,N-1,A);
		for(int j=1;j<=deg;j++) A[j][deg+i]=a[j];
	}
}
void read(void){
	scanf("%d",&N);
	int a,b;
	for(int i=1;i<N;i++){
		scanf("%d%d",&a,&b);
		c[a].push_back(b);
		c[b].push_back(a);
	}
}
int main(){
	freopen("nt2012_coloring.in","r",stdin);
	freopen("nt2012_coloring.out","w",stdout);
	read();
	DFS(1);
	printf("%d\n",f[1][0]);
	return 0;
}