BZOJ 3197 Sdoi 2013 assassin 동적 기획 + 트리 구성 + 비용 흐름

제목 대의: 한 그루의 나무와 두 조의 값을 정하고 첫 번째 조의 값을 최소한 몇 개 바꾼 후에 이 나무는 재표시를 거친 후에 두 번째 조의 값과 같다
이 문제는 솜씨가 아주 뛰어나다--
우선 3162와 같은 처리 방식을 가지고 이 나무의 중심을 뿌리로 삼고 중심이 두 개면 한 뿌리를 새로 만들고 이 두 중심을 향해
f[x][y]는 x가 있는 하위 트리의 첫 번째 그룹 값과 y가 있는 하위 트리의 두 번째 그룹 값이 일치하는 최소 비용을 나타낸다
이동의 필수 조건은 x가 있는 하위 트리와 y가 있는 하위 트리가 같고 x와 y의 깊이가 같다는 것이다
후효성을 확보하기 위해서 x의 모든 하위 노드와 y의 모든 하위 노드 사이의 최소 비용은 반드시 이미 구해야 한다
그러면 우리는 노드를 깊이의 상반수로 첫 번째 키 값을,Hash값은 두 번째 키 값으로 정렬하여 왼쪽에서 오른쪽으로 열거하는 깊이가Hash와 같은 점으로 이동한다
이분도 최대권 완비 매칭
매번 x를 y로 옮길 때마다 우리는 x와 y로 구성된 자수 사이를 일일이 일치시켜야 한다. 그래서 우리는 이분도의 가장 큰 권한을 가진 완비 일치로 이 물건을 만들 수 있다.
KM을 모르는구나. QAQ. 그래서 비용 흐름을 썼어요. -
코드를 4.6KB로 썼는데 별로 안 맞춰서 1A가 됐어요. - 감동적이에요.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 710
#define ORIGIN 233
#define BASE 233333333
#define S 0
#define T 29
#define INF 0x3f3f3f3f
using namespace std;
int n,f1[M],f2[M],f[M][M];
pair<pair<int,unsigned long long>,int> sorter[M];
//      ，       
namespace Trees_Isomorphism{
	struct abcd{
		int to,next;
	}table[M<<1];
	int head[M],tot=1;
	int root,cg[2];
	int fa[M],size[M],dpt[M];
	unsigned long long hash[M];
	void Add(int x,int y)
	{
		table[++tot].to=y;
		table[tot].next=head[x];
		head[x]=tot;
	}
	void Get_Centre_Of_Gravity(int x,int from)
	{
		int i,flag=1;
		size[x]=1;
		for(i=head[x];i;i=table[i].next)
			if(table[i].to!=from)
			{
				Get_Centre_Of_Gravity(table[i].to,x);
				size[x]+=size[table[i].to];
				if(size[table[i].to]<<1>n)
					flag=0;
			}
		if(n-size[x]<<1>n)
			flag=0;
		if(flag)
			(cg[0]?cg[1]:cg[0])=x;
	}
	void Get_Hash(int x)
	{
		static int stack[M];
		int i,top=0;
		dpt[x]=dpt[fa[x]]+1;
		for(i=head[x];i;i=table[i].next)
			if(table[i].to!=fa[x])
			{
				fa[table[i].to]=x;
				Get_Hash(table[i].to);
			}
		for(i=head[x];i;i=table[i].next)
			if(table[i].to!=fa[x])
				stack[++top]=hash[table[i].to];
		sort(stack+1,stack+top+1);
		hash[x]=ORIGIN;
		for(i=1;i<=top;i++)
			(((hash[x]*=BASE)^=stack[i])+=stack[i])^=stack[i];
	}
}
namespace Min_Cost_Max_Flow{
	struct abcd{
		int to,flow,cost,next;
	}table[10100];
	int head[30],tot=1;
	int ans;
	void Initialize()
	{
		memset(head,0,sizeof head);
		tot=1;ans=0;
	}
	void Add(int x,int y,int f,int c)
	{
		table[++tot].to=y;
		table[tot].flow=f;
		table[tot].cost=c;
		table[tot].next=head[x];
		head[x]=tot;
	}
	void Link(int x,int y,int f,int c)
	{
		Add(x,y,f,c);
		Add(y,x,0,-c);
	}
	bool Edmonds_Karp()
	{
		static int q[65540],flow[30],cost[30],from[30];
		static unsigned short r,h;
		static bool v[M];
		int i;
		memset(cost,0x3f,sizeof cost);
		flow[S]=INF;cost[S]=0;q[++r]=S;
		while(r!=h)
		{
			int x=q[++h];v[x]=0;
			for(i=head[x];i;i=table[i].next)
				if(table[i].flow&&cost[table[i].to]>cost[x]+table[i].cost)
				{
					cost[table[i].to]=cost[x]+table[i].cost;
					flow[table[i].to]=min(flow[x],table[i].flow);
					from[table[i].to]=i;
					if(!v[table[i].to])
						v[table[i].to]=1,q[++r]=table[i].to;
				}
		}
		if(cost[T]==INF) return false;
		ans+=cost[T]*flow[T];
		for(i=from[T];i;i=from[table[i^1].to])
			table[i].flow-=flow[T],table[i^1].flow+=flow[T];
		return true;
	}
}
using namespace Trees_Isomorphism;
bool Compare(int x,int y)
{
	return hash[x] < hash[y];
}
int DP(int x,int y)
{
	static int stack1[M],stack2[M];
	int i,j,k,l,top1=0,top2=0;
	for(i=head[x];i;i=table[i].next)
		if(table[i].to!=fa[x])
			stack1[++top1]=table[i].to;
	for(i=head[y];i;i=table[i].next)
		if(table[i].to!=fa[y])
			stack2[++top2]=table[i].to;
	sort(stack1+1,stack1+top1+1,Compare);
	sort(stack2+1,stack2+top2+1,Compare);
	Min_Cost_Max_Flow::Initialize();
	for(i=1;i<=top1;i=j)
	{
		for(j=i+1;j<=top1&&hash[stack1[i]]==hash[stack1[j]];j++);
		for(k=i;k<j;k++)
			for(l=i;l<j;l++)
				Min_Cost_Max_Flow::Link(k,top1+l,1,f[stack1[k]][stack2[l]]);
	}
	for(i=1;i<=top1;i++)
	{
		Min_Cost_Max_Flow::Link(S,i,1,0);
		Min_Cost_Max_Flow::Link(i+top1,T,1,0);
	}
	while( Min_Cost_Max_Flow::Edmonds_Karp() );
	return Min_Cost_Max_Flow::ans+(f1[x]^f2[y]);
}
int main()
{
	int i,j,x,y;
	cin>>n;
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		Add(x,y);Add(y,x);
	}
	for(i=1;i<=n;i++)
		scanf("%d",&f1[i]);
	for(i=1;i<=n;i++)
		scanf("%d",&f2[i]);
	Get_Centre_Of_Gravity(1,0);
	if(cg[1])
	{
		root=++n;
		for(i=head[cg[0]];i;i=table[i].next)
			if(table[i].to==cg[1])
			{
				table[i].to=table[i^1].to=n;
				break;
			}
		Add(n,cg[0]);
		Add(n,cg[1]);
	}
	else root=cg[0];
	Get_Hash(root);
	for(i=1;i<=n;i++)
		sorter[i]=make_pair(make_pair(-dpt[i],hash[i]),i);
	sort(sorter+1,sorter+n+1);
	for(i=1;i<=n;i=j)
	{
		for(j=i+1;j<=n&&sorter[i].first==sorter[j].first;j++);
		for(x=i;x<j;x++)
			for(y=i;y<j;y++)
				f[sorter[x].second][sorter[y].second]=DP(sorter[x].second,sorter[y].second);
	}
	cout<<f[root][root]<<endl;
	return 0;
}