Chrysanthemum's Blog

本题本人现场就A了哟！！

比较简单，就不多讲了，注意一下第二问的一些细节就好了。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,u,v,tot,edgenum,ans,a[100010],f[100010],num[100010],q[100010],p[100010];
int vet[200010],next[200010],head[200010],ok[100010];
void add(int u,int v)
{
	edgenum++;
	vet[edgenum]=v;
	next[edgenum]=head[u];
	head[u]=edgenum;
}
bool cmp(const int x,const int y){return f[x]>f[y];}
void dfs(int u,int fa)
{
	int tot1=tot;
	f[u]=a[u];
	for (int e=head[u];e;e=next[e])
	{
		int v=vet[e];
		if (v!=fa) 
		{
			dfs(v,u);
			if (u==1){if (f[v]>0) {ans+=f[v];ok[1]=ok[1]|ok[v];}if (f[v]==0) ok[1]=1;}else q[++tot]=v;
		}
	}
	if (tot==tot1) return;
	if (u==1) return;
	for (int i=tot1+1;i<=tot;i++)
		p[i]=q[i];
	sort(p+tot1+1,p+tot+1,cmp);
	for (int i=tot1+1;i<=tot;i++)
	if (i-tot1>num[u]){if (i>tot1+1&&f[p[i]]==f[p[i-1]])ok[u]=1;break;}else if (f[p[i]]==0) ok[u]=1;else if (f[p[i]]<0) break;else {f[u]+=f[p[i]];ok[u]=ok[u]|ok[p[i]];}
	tot=tot1;
}
int main()
{
	freopen("salesman.in","r",stdin);
	freopen("salesman.out","w",stdout);
	scanf("%d",&n);
	for (int i=2;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=2;i<=n;i++)
	{
		scanf("%d",&num[i]);
		num[i]--;
	}
	for (int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	ans=0;
	dfs(1,0);
	printf("%d\n",ans);
	if (ok[1]) printf("solution is not unique\n");else printf("solution is unique\n");
}

第一次写省队难度题目的题解，心里也是有点激动的辣！！！

题意：给你m棵树，让你先简化一下每棵树（这乱搞一下），然后把不同构（同构的定义不知道的话就去百度一下吧。。）的所有简化树的节点数从小到大输出来。

题解：我们只要把每种不同构的树用不同的权值表示，这样这道题就迎刃而解了。那么如何表示这个权值呢？请教了一下金牌爷gonens，。我们可以用类似于拓扑排序的方法来计算这个权值。先把所有度为1的点放入队列中，令他们的权值都为1。然后一层一层往上搜，每次发现当前的这个点度变为1时，就计算一下他的权值，把他儿子（注意：这里的儿子是有限制的：已经算好权值且和他不在同一层）的权值从小到大排个序，然后第一个数乘以A¹，第二个数乘以A²，…，第n个数乘以Aⁿ，A为自己定一个质数，然后加起来取模一个P就好了。至此，此题就顺利解决了。

不要问我一开始为什么T了，边表数组没开两倍啊。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include <iostream>
#define mod 1000000007
using namespace std;
typedef long long ll;
struct node{ll hash;int num;}p[25];
int n,m,u,v,edgenum,num;
ll mi[10010];
int vet[20010],next[20010],head[20010],flag[10010],fa[10010],d[10010],du[10010],id[10010],q[10010],dep[10010],P[25];
ll f[10010],a[10010];
void add(int u,int v)
{
	edgenum++;
	vet[edgenum]=v;
	next[edgenum]=head[u];
	head[u]=edgenum;
}
void dfs(int u,int pre)
{
	flag[u]=1;
	fa[u]=pre;
	if (d[u]!=2) id[u]=++num;else id[u]=pre;
	for (int e=head[u];e>0;e=next[e])
	{
		int v=vet[e];
		if (!flag[v])
			dfs(v,id[u]);	
	}
}
ll calc(int u)
{
	int cnt=0;
	for (int e=head[u];e;e=next[e])
	{
		int v=vet[e];
		if (flag[v]&&dep[v]!=dep[u])
			a[cnt++]=f[v];
	}
	sort(a,a+cnt);
	ll ans=0;
	for (int i=0;i<cnt;i++)
		ans=(ans+mi[i]*a[i]%mod)%mod;
	return ans;
}
bool cmp1(const node x,const node y){return x.hash<y.hash;}
int main()
{
	scanf("%d",&m);
	mi[0]=1;
	for (int i=1;i<=10000;i++)
		mi[i]=mi[i-1]*10003%mod;
	for (int k=1;k<=m;k++)
	{
		scanf("%d",&n);
		memset(d,0,sizeof(d));
		memset(head,0,sizeof(head));
		edgenum=0;
		for (int i=1;i<n;i++)
		{
			scanf("%d%d",&u,&v);
			d[u]++;d[v]++;
			add(u,v);add(v,u);
		}
		num=0;
		memset(flag,0,sizeof(flag));
		memset(fa,0,sizeof(fa));
		for (int i=1;i<=n;i++)
		if (d[i]!=2){dfs(i,0);break;}
		memset(head,0,sizeof(head));
		memset(du,0,sizeof(du));
		edgenum=0;
		for (int i=1;i<=n;i++)
		if (id[i]!=fa[i]&&fa[i]!=0){add(id[i],fa[i]);add(fa[i],id[i]);du[id[i]]++;du[fa[i]]++;}
		int p1=0,p2=0;
		memset(dep,0,sizeof(dep));
		memset(flag,0,sizeof(flag));
		for (int i=1;i<=num;i++)
		if (du[i]==1){q[++p2]=i;dep[i]=0;flag[i]=1;f[i]=1;}
		while (p1<p2)
		{
			u=q[++p1];
			for (int e=head[u];e;e=next[e])
			{
				int v=vet[e];
				if (!flag[v])
				{
					du[v]--;
					if (du[v]==1)
					{
						flag[v]=1;
						dep[v]=dep[u]+1;
						q[++p2]=v;
						f[v]=calc(v);
					}
				}
			}
		}
		sort(f+1,f+num+1);
		for (int i=1;i<=num;i++)
			p[k].hash=(p[k].hash+f[i]*mi[i-1]%mod)%mod;
		p[k].num=num;
	}
	sort(p+1,p+m+1,cmp1);
	n=1;
	P[1]=p[1].num;
	for (int i=2;i<=m;i++)
	if (p[i].hash!=p[i-1].hash) P[++n]=p[i].num;
	printf("%d\n",n);
	sort(P+1,P+n+1);
	for (int i=1;i<n;i++) printf("%d ",P[i]);
	printf("%d\n",P[n]);
}