「BZOJ3162」独钓寒江雪

2015年1月28日4,3517

Description

题解

参照2007杨弋论文

vfk的博客 http://vfleaking.blog.163.com/blog/static/17480763420134452440444/

太神了orzorzorz

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define mod 1000000007
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,root,cnt=1;
int h[2],mn=inf;
int last[500005],size[500005];
int st[500005],top;
ll ine[500005],f[500005][2],ans;
unsigned ll H[500005];
struct edge{
	int to,next;
}e[1000005];
void insert(int u,int v)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
bool cmp(int x,int y)
{
	return H[x]>H[y];
}
void dfs(int x,int fa)
{
	size[x]=1;
	int tmp=0;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa)
		{
			dfs(e[i].to,x);
			size[x]+=size[e[i].to];
			tmp=max(tmp,size[e[i].to]);
		}
	tmp=max(n-size[x],tmp);
	if(tmp<mn)h[0]=x,h[1]=0,mn=tmp;
	else if(tmp==mn)h[1]=x;
}
int C(int n,int m)
{
	ll tmp=1;n%=mod;
	for(int i=1;i<=m;i++)
		tmp=tmp*(n-i+1)%mod*ine[i]%mod;
	return tmp;
}
int color(int n,ll m)
{
	return C(n+m-1,n);
}
void dp(int x,int fa)
{
	f[x][0]=f[x][1]=1;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa)
			dp(e[i].to,x);
	top=0;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa)
			st[top++]=e[i].to;
	sort(st,st+top,cmp);
	int j;
	for(int i=0;i<top;i=j)
	{
		for(j=i+1;j<top&&H[st[i]]==H[st[j]];j++);
		f[x][0]=f[x][0]*color(j-i,f[st[i]][0]+f[st[i]][1])%mod;
	   	f[x][1]=f[x][1]*color(j-i,f[st[i]][0])%mod;
	}
	H[x]=19;
	for(int i=0;i<top;i++)
		H[x]=(H[x]*9875321+17*H[st[i]]);
}
void pre()
{
	ine[1]=1;
	for(int i=2;i<=n;i++)
		ine[i]=ine[mod%i]*(mod-mod/i)%mod;
}
int main()
{
	n=read();pre();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
		insert(v,u);
	}
	dfs(1,0);
	if(h[1])
	{
		for(int i=last[h[0]];i;i=e[i].next)
			if(e[i].to==h[1])
			{
				e[i].to=e[i^1].to=root=n+1;
			}
		insert(n+1,h[0]);insert(n+1,h[1]);
	}
	else root=h[0];
	dp(root,0);
	if(!h[1])
		ans=(f[root][0]+f[root][1])%mod;
	else 
	{
		int x=h[0],y=h[1];
		if(H[x]==H[y])
			ans=(f[x][0]*f[y][1]%mod+color(2,f[x][0]))%mod;
		else 
			ans=(f[x][0]*f[y][0]%mod+f[x][1]*f[y][0]%mod+f[x][0]*f[x][1]%mod)%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define mod 1000000007

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,root,cnt=1;

int h[2],mn=inf;

int last[500005],size[500005];

int st[500005],top;

ll ine[500005],f[500005][2],ans;

unsigned ll H[500005];

struct edge{

int to,next;

}e[1000005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

}

bool cmp(int x,int y)

{

return H[x]>H[y];

}

void dfs(int x,int fa)

{

size[x]=1;

int tmp=0;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa)

{

dfs(e[i].to,x);

size[x]+=size[e[i].to];

tmp=max(tmp,size[e[i].to]);

}

tmp=max(n-size[x],tmp);

if(tmp<mn)h[0]=x,h[1]=0,mn=tmp;

else if(tmp==mn)h[1]=x;

}

int C(int n,int m)

{

ll tmp=1;n%=mod;

for(int i=1;i<=m;i++)

tmp=tmp*(n-i+1)%mod*ine[i]%mod;

return tmp;

}

int color(int n,ll m)

{

return C(n+m-1,n);

}

void dp(int x,int fa)

{

f[x][0]=f[x][1]=1;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa)

dp(e[i].to,x);

top=0;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa)

st[top++]=e[i].to;

sort(st,st+top,cmp);

int j;

for(int i=0;i<top;i=j)

{

for(j=i+1;j<top&&H[st[i]]==H[st[j]];j++);

f[x][0]=f[x][0]*color(j-i,f[st[i]][0]+f[st[i]][1])%mod;

f[x][1]=f[x][1]*color(j-i,f[st[i]][0])%mod;

}

H[x]=19;

for(int i=0;i<top;i++)

H[x]=(H[x]*9875321+17*H[st[i]]);

}

void pre()

{

ine[1]=1;

for(int i=2;i<=n;i++)

ine[i]=ine[mod%i]*(mod-mod/i)%mod;

}

int main()

{

n=read();pre();

for(int i=1;i<n;i++)

{

int u=read(),v=read();

insert(u,v);

insert(v,u);

}

dfs(1,0);

if(h[1])

{

for(int i=last[h[0]];i;i=e[i].next)

if(e[i].to==h[1])

{

e[i].to=e[i^1].to=root=n+1;

}

insert(n+1,h[0]);insert(n+1,h[1]);

}

else root=h[0];

dp(root,0);

if(!h[1])

ans=(f[root][0]+f[root][1])%mod;

else

{

int x=h[0],y=h[1];

if(H[x]==H[y])

ans=(f[x][0]*f[y][1]%mod+color(2,f[x][0]))%mod;

else

ans=(f[x][0]*f[y][0]%mod+f[x][1]*f[y][0]%mod+f[x][0]*f[x][1]%mod)%mod;

}

printf("%lld\n",ans);

return 0;

}

« 「BZOJ3611」[HEOI2014] 大工程「BZOJ2815」[ZJOI2012] 灾难 »

sunzeyu

vfk的博客上只有标程和数据啊，没看到题解……

hzwer

是有个pdf吧

Chenyao

嗯。。。诡异。。。把你代码中cmp的>换成<就会wa一半，是因为冲突了嘛。。。

hzwer

这。。。我不懂啊有这种事

Recursion

从大到小排序可以使深度越大的点hash的幂次越高，如果从小到大冲突率会变大

Chenyao

你代码中是直接求出树的重心来当做中心嘛？那树的中心和重心是一个点如何证明呢？我没有搜到相关资料，求证明或链接>_<

hzwer

好像vfk的题解有吧

hzwer.com _ Home | http://hzwer.com

「BZOJ3162」独钓寒江雪

Description

题解

分类目录

热门文章

Myfriends

近期评论