记录编号	532871	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2012] 道路染色	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	1.047 s
提交时间	2019-06-05 16:28:32	内存使用	3.38 MiB

#include <bits/stdc++.h>
#define N 155
using namespace std;
ifstream fin("nt2012_coloring.in");
ofstream fout("nt2012_coloring.out");
const int inf=(1<<29);

int dp[N][N]={0};
int nn,mm;
vector<int> G[N],F[N];
bool vis[N];

class KM
{
public:
	bool vis[2*N];
	bool ok[2*N];
	int f[N][2*N];
	int slack[2*N],match[2*N],label[2*N];
	int m,n;
	void clear(int sx,int sy)
	{
		m=sx;n=sy;
		//fout<<m+1<<' '<<m+n<<endl;
		memset(vis,0,sizeof(vis));
		memset(f,0,sizeof(f));
		memset(slack,0,sizeof(slack));
		memset(ok,0,sizeof(ok));
		memset(label,0,sizeof(label));
		memset(match,0,sizeof(match));
	}
	bool find(int u)
	{
		vis[u]=1;
		for(int v=m+1;v<=m+n;v++)
		{
			if(vis[v]||!f[u][v])continue;
			int t=label[u]+label[v]-f[u][v];
			if(!t)
			{
				vis[v]=1;
				if(!match[v]||find(match[v]))
				{
					match[v]=u;
					return 1;
				}
			}
			else slack[v]=min(slack[v],t);
		}
		return 0;
	}
	void KMP()
	{
		int i,j;
		for(i=1;i<=m;i++)
		{
			label[i]=-inf;
			for(j=m+1;j<=m+n;j++)label[i]=max(label[i],f[i][j]);
		}
		for(i=1;i<=m;i++)
		{
			if(!ok[i])continue;
			while(true)
			{
				for(j=1;j<=m+n;j++)vis[j]=0;
				for(j=m+1;j<=m+n;j++)slack[j]=inf;
				if(find(i))break;
				int d=inf;
				for(j=m+1;j<=m+n;j++)if(!vis[j])d=min(d,slack[j]);
				for(j=1;j<=m;j++)if(vis[j])label[j]-=d;
				for(j=m+1;j<=m+n;j++)if(vis[j])label[j]+=d;
			}
		}
	}
	int count()
	{
		int ans=0;
		for(int i=m+1;i<=m+n;i++)if(match[i])ans+=f[match[i]][i];
		return ans;
	}
	void add(int u,int v,int w)
	{
		f[u][v]=w;
		ok[u]=true;
		//fout<<u<<' '<<v<<' '<<w<<endl;
	}
};
int build(int u,int color)
{
	KM S;
	S.clear(F[u].size(),mm);
	//fout<<u<<':'<<F[u].size()<<':'<<mm<<':'<<color<<endl;
	for(int i=0;i<F[u].size();i++)
	{
		int v=F[u][i];
		for(int j=1;j<=mm;j++)if(j!=color)S.add(i+1,j+F[u].size(),200000-dp[v][j]);
	}
	S.KMP();

	for(int i=0;i<F[u].size();i++)
	{
		int v=F[u][i];
		for(int j=1;j<=mm;j++)S.add(i+1,j+F[u].size(),dp[v][j]);
	}
	return S.count()+color;
}
void DFS(int u)
{
	vis[u]=1;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(!vis[v])
		{
			F[u].push_back(v);
			DFS(v);
		}
	}
	if(!F[u].size())for(int i=1;i<=mm;i++)dp[u][i]=i;
	else if(u==1)dp[u][0]=build(u,0);
	else for(int i=1;i<=mm;i++)dp[u][i]=build(u,i);
}
void read()
{
	fin>>nn;
	for(int i=1;i<nn;i++)
	{
		int u,v;
		fin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
		//fout<<u<<' '<<v<<endl;
	}
}
void work()
{
	for(int i=1;i<=nn;i++)
	{
		for(int j=1;j<=nn;j++)
		{
			dp[i][j]=inf;
		}
	}
	mm=nn-1;
	DFS(1);
	fout<<dp[1][0]<<endl;
}
int main()
{
	read();
	work();
	return 0;
}