BZOJ4757

来自蒟蒻XXJ的做题记录

突如其来的幸福.jpg

真的伤

题解见 http://blog.csdn.net/samjia2000/article/details/51762811

#include<bits/stdc++.h>
#define mem(i,j) memset(i,j,sizeof(i))
using namespace std;
typedef unsigned long long ll;
const int MAXN=100010;
const ll Basic=81119;
inline int in(){
	int a(0);
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
	return a;
}
int n,ans;
int siz[MAXN];
ll hash[MAXN],_hash[MAXN];
int ru[MAXN];
map<ll,bool> mm;
struct Index{
	int d;ll tmp;
	Index(int d,ll tmp){this->d=d;this->tmp=tmp;}
};
vector<Index> sum[MAXN];
struct Edge{
	int head[MAXN],to[2*MAXN],nex[2*MAXN],top1;
	Edge(){
		mem(head,-1);
		top1=0;
	}
	void add(int a,int b){
		nex[top1]=head[a];
		head[a]=top1;
		to[top1++]=b;
		nex[top1]=head[b];
		head[b]=top1;
		to[top1++]=a;
	}
}e[2];
void input(){
	n=in();
	for(int i=1;i<n;i++){
		int a,b;
		a=in();
		b=in();
		e[0].add(a,b);
	}
	for(int i=1;i<=n;i++){
		int a,b;
		a=in();
		b=in();
		e[1].add(a,b);
		ru[a]++;ru[b]++;
	}
}
bool cmp(Index x,Index y){
	return x.tmp>y.tmp;
}
ll Get(int here,int nouse){
	int lth=sum[here].size();
	ll pre(0);
	for(int i=0;i<lth;i++){
		if(sum[here][i].d==nouse) continue;
		pre=pre*Basic+sum[here][i].tmp;
	}
	pre*=Basic;//Õâ¸öÇóµÄÊÇ×ÓÊ÷¡­¡­×ÓÊ÷µÄ´óС¾ÍÊÇ¡­¡­
	pre+=n-siz[nouse];
	return pre;
}
void dfs1(int here,int fa){
	siz[here]=1;
	for(int i=e[0].head[here]; i!=-1; i=e[0].nex[i]) {
		int go=e[0].to[i];
		if(go==fa) continue;
		dfs1(go,here);
		siz[here]+=siz[go];
		sum[here].push_back(Index(go,hash[go]));
	}
	ll pre(0);
	sort(sum[here].begin(),sum[here].end(),cmp);
	int lth=sum[here].size();
	for(int i=0;i!=lth;i++) pre=pre*Basic+sum[here][i].tmp;
	pre*=Basic;
	pre+=siz[here];
	hash[here]=pre;
}
void dfs2(int here,int fa){
	if(here!=1){
		ll hhh(Get(fa,here));//´ÓËûµÄ¸¸Ç×´«ÏÂÀ´µÄ×ÓÊ÷µÄhashÖµ
		sum[here].push_back(Index(fa,hhh));
		sort(sum[here].begin(),sum[here].end(),cmp);
	}
	ll ppap(0),lth=sum[here].size();//Õâ¸öÊÇÓÃÀ´Çó½Úµã×÷Ϊ¸ùʱµÄhashÖµµÄ
	for(int i=0;i<lth;i++){
		ppap=ppap*Basic+sum[here][i].tmp;
	}
	ppap*=Basic;
	ppap+=n;
	_hash[here]=ppap;
	for(int i=e[0].head[here];i!=-1;i=e[0].nex[i]){
		int go=e[0].to[i];
		if(go==fa) continue;
		dfs2(go,here);
	}
}
void _dfs1(int here,int fa){
	siz[here]=1;
	for(int i=e[1].head[here];i!=-1;i=e[1].nex[i]) {
		int go=e[1].to[i];
		if(go==fa) continue;
		_dfs1(go,here);
		siz[here]+=siz[go];
		sum[here].push_back(Index(go,hash[go]));
	}
	ll pre(0);
	int lth=sum[here].size();
	sort(sum[here].begin(),sum[here].end(),cmp);
	for(int i=0;i<lth;i++) pre=pre*Basic+sum[here][i].tmp;
	pre*=Basic;
	pre+=siz[here];
	hash[here]=pre;
}
void _dfs2(int here,int fa){
	if(here!=1){
		ll hhh(Get(fa,here));//´ÓËûµÄ¸¸Ç×´«ÏÂÀ´µÄ×ÓÊ÷µÄhashÖµ
		sum[here].push_back(Index(fa,hhh));
		sort(sum[here].begin(),sum[here].end(),cmp);
	}
	for(int i=e[1].head[here];i!=-1;i=e[1].nex[i]){
		int go=e[1].to[i];
		if(go==fa) continue;
		_dfs2(go,here);
	}
}
void init(){
	mem(hash,0);mem(_hash,0);mem(siz,0);
	for(int i=1;i<=n+1;i++) sum[i].clear();
	++n;
}
void xxj(){
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++) mm[_hash[i]]=1;
	init();
	_dfs1(1,0);
	_dfs2(1,0);
}
void output(){
	for(int i=1;i<=n+1;i++){
		if(sum[i].size()-1) continue;
		if(mm[sum[i][0].tmp]) cout<<i<<endl,exit(0);
	}
}

int main(){
	input();
	xxj();
	output();
	return 0;
}