Submission #3089459

---

Source Code Expand

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	/*まず、半径点を決める
	そこからののぼりくだりを決める
	半径点は全探索する(O(n^2))
	そしてオイラーツアーからの₯で優勝
	*/
	int n,i,j;cin>>n;
	int R=869120;
	vector<vector<int>>go(n);
	for(i=0;i<n-1;i++){
		int a,b;cin>>a>>b;a--;b--;
		go[a].pub(b);
		go[b].pub(a);
	}
	vector<int>dis;
	int chuA=1,chuB=-1;
	for(i=0;i<n;i++){
		stack<pair<int,int>>que;
		que.push(mp(i,0));
		bool ok=1;
		vector<int>gdis(n,-1);
		int nowR=0;
		while(que.size()){
			auto pa=que.top();
			que.pop();
			gdis[pa.fir]=pa.sec;
			maxeq(nowR,pa.sec);
			if(R<pa.sec){ok=0;break;}
			for(auto it:go[pa.fir]){
				if(gdis[it]!=-1){continue;}
				que.push(mp(it,pa.sec+1));
			}
		}
		if(ok){
			dis=gdis;
			if(R>nowR){R=nowR;chuA=i;chuB=-1;}//更新
			else{chuB=i;}//タイ
		}
	}
	//これで直径とその場所がわかった
	//半径が二つあるパターンは特別なことになる
	if(chuB!=-1){
		queue<pair<int,int>>que;
		que.push(mp(chuA,0));
		que.push(mp(chuB,0));
		bool ok=1;
		vector<int>gdis(n,-1);
		while(que.size()){
			auto pa=que.front();
			que.pop();
			if(gdis[pa.fir]!=-1){continue;}
			gdis[pa.fir]=pa.sec;
			for(auto it:go[pa.fir]){
				
				que.push(mp(it,pa.sec+1));
			}
		}
		dis=gdis;
	}
	//for(j=0;j<n;j++){cerr<<dis[j];}cerr<<endl;
	//さらに子の番号<親番号 を満たすように名前を付け直す
	vector<pair<int,int>>sodis(n);
	for(i=0;i<n;i++){sodis[i]=mp(dis[i],i);}
	SO(sodis);REV(sodis);//sodis[i].sec は新しい->古い
	vector<int>siban(n);//古い->新しい
	for(i=0;i<n;i++){siban[sodis[i].sec]=i;}//
	vector<vector<llint>>dp(n,vector<llint>(R+1));
	vector<vector<llint>>ep(n,vector<llint>(R));
	//半径の場所で↑と↓を完全に振り分ける、大仕事をする
	//dp[i][j]は、i番目の部分木+親への辺
	//↑はj個まで、↓はR+1-dis[i]-j個までの方法
	//epは↓はR-dis[i]-j個までの方法
	for(i=0;i<n;i++){
		for(j=0;j<=R-dis[sodis[i].sec];j++){dp[i][j]=1;}
		for(j=0;j< R-dis[sodis[i].sec];j++){ep[i][j]=1;}
		for(auto it:go[sodis[i].sec]){
			int ter=siban[it];
			if(sodis[i].fir>=sodis[ter].fir){continue;}//terは親
			for(j=0;j<=R;j++){dp[i][j]*=dp[ter][j];dp[i][j]%=mod;}
			for(j=0;j< R;j++){ep[i][j]*=ep[ter][j];ep[i][j]%=mod;}
		}
		//さいごにえい!
		//for(j=0;j<=R-dis[sodis[i].sec];j++){cerr<<dp[i][j]<<" ";}cerr<<endl;
		//for(j=0;j< R-dis[sodis[i].sec];j++){cerr<<ep[i][j]<<" ";}cerr<<endl;
		if(i!=n-1&&(chuB==-1||i!=n-2)){
			for(j=R-dis[sodis[i].sec];j>=0;j--){dp[i][j+1]+=dp[i][j];}
			for(j=R-dis[sodis[i].sec]-1;j>=0;j--){ep[i][j+1]+=ep[i][j];}
		}
	}
	//そして答えを足す
	if(chuB==-1){
		llint ans=0;
		for(j=R;j>=0;j--){ans+=dp[n-1][j];}
		ans%=mod;
		cout<<ans<<endl;
	}else{
		//strictなdpにする
		for(j=0;j<R;j++){
			dp[n-1][j]-=ep[n-1][j];dp[n-1][j+1]-=ep[n-1][j];
			dp[n-2][j]-=ep[n-2][j];dp[n-2][j+1]-=ep[n-2][j];
		}
		//for(j=0;j<=R;j++){cerr<<dp[n-2][j]<<endl;}
		llint ans=0;
		for(j=0;j<R-1;j++){
			ans+=ep[n-1][j]*ep[n-2][j+1];ans+=ep[n-1][j+1]*ep[n-2][j];ans%=mod;
		}
		for(j=0;j<R;j++){
			ans+=dp[n-1][j]*ep[n-2][j];ans+=dp[n-1][j+1]*ep[n-2][j];ans%=mod;
			ans+=ep[n-1][j]*dp[n-2][j];ans+=ep[n-1][j]*dp[n-2][j+1];ans%=mod;
			ans+=ep[n-1][j]*ep[n-2][j]*2;ans%=mod;
		}
		ans+=mod;ans%=mod;
		cout<<ans<<endl;
	}
}

Submission Info

Judge Result