Submission #1734758

---

Source Code Expand

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
vector<int>g[1100];
long long dp[1100][1100];
int bfs[1100];
int pr[1100];
int dep[1100];
int D;
int T=510;
int lis[1100];
int dist[1100];
int dc(int a,int b){
	int ret=0;
	int f=0;
	for(int i=0;i<g[a].size();i++){
		if(b==g[a][i])continue;
		dist[g[a][i]]=dist[a]+1;
		int q=dc(g[a][i],a)+1;
		ret=max(ret,q);
	}
	return ret;
}
void dfs(int a,int b){
	for(int i=-(D-dist[a]);i<=D-dist[a];i++){
		dp[a][T+i]=1;
	}
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		dfs(g[a][i],a);
		for(int j=0;j<1100;j++){
			long long tmp=0;
			if(j)tmp=(tmp+dp[g[a][i]][j-1])%mod;
			if(j+1<1100)tmp=(tmp+dp[g[a][i]][j+1])%mod;
			dp[a][j]=dp[a][j]*tmp%mod;
		}
	}
}
int n;
long long calc(int a){
	dist[a]=0;
	dc(a,-1);
	for(int i=0;i<n;i++)for(int j=0;j<1100;j++)dp[i][j]=0;
	dfs(a,-1);
	long long ret=0;
	for(int i=0;i<1100;i++){
		ret=(ret+dp[a][i])%mod;
	}
	return ret;
}
int main(){
	int a;
	scanf("%d",&a);
	n=a;
	for(int i=0;i<a-1;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	long long r=1;
	for(int i=0;i<a-1;i++)r=r*2%mod;
	queue<int>Q;
	Q.push(0);
	for(int i=0;i<a;i++)bfs[i]=-1;
	bfs[0]=0;
	while(Q.size()){
		int at=Q.front();
		Q.pop();
		for(int i=0;i<g[at].size();i++){
			int to=g[at][i];
			if(bfs[to]!=-1)continue;
			bfs[to]=bfs[at]+1;
			Q.push(to);
		}
	}
	int sz=0;
	int mv=0;
	for(int i=0;i<a;i++){
		if(bfs[mv]<bfs[i])mv=i;
	}
	for(int i=0;i<a;i++)bfs[i]=-1;
	Q.push(mv);
	bfs[mv]=0;
	pr[mv]=-1;
	while(Q.size()){
		int at=Q.front();Q.pop();
		for(int i=0;i<g[at].size();i++){
			int to=g[at][i];
			if(bfs[to]!=-1)continue;
			Q.push(to);
			bfs[to]=bfs[at]+1;
			pr[to]=at;
		}
	}
	int di=0;
	int da=0;
	for(int i=0;i<a;i++){
		if(di<bfs[i]){
			di=bfs[i];
			da=i;
		}
	}
	int at=da;
	while(~at){
		lis[sz++]=at;
		at=pr[at];
	}
	long long ret;
	if(di%2==0){
		D=sz/2;
		ret=calc(lis[sz/2]);
	}else{
		D=(sz+1)/2;
		ret=(calc(lis[sz/2-1])+calc(lis[sz/2]))%mod;
		g[n].push_back(lis[sz/2-1]);
		g[n].push_back(lis[sz/2]);
		for(int i=0;i<g[lis[sz/2-1]].size();i++){
			if(g[lis[sz/2-1]][i]==lis[sz/2])g[lis[sz/2-1]][i]=n;
		}
		for(int i=0;i<g[lis[sz/2]].size();i++){
			if(g[lis[sz/2]][i]==lis[sz/2-1])g[lis[sz/2]][i]=n;
		}
		ret=(ret+mod-calc(n))%mod;
	}
	printf("%lld\n",ret);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:64:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&a);
                ^
./Main.cpp:67:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int p,q;scanf("%d%d",&p,&q);p--;q--;
                              ^

Judge Result