Submission #1138308
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
//make_tuple emplace_back next_permutation push_back make_pair second first setprecision
#if MYDEBUG
#include "lib/cp_debug.h"
#else
#define DBG(...) ;
#endif
using LL = long long;
constexpr LL LINF=334ll<<53;
constexpr int INF=15<<26;
constexpr LL MOD=1E9+7;
using Graph = vector<vector<int>>;
struct Problem{
LL n;
Graph t;
vector<int> height;
vector<LL> fac,inv;
Problem(LL n):n(n),t(n),height(n),fac(2020),inv(2020){};
int maxd,D;
int bfs(int s){
vector<int> vis(n),ord;
queue<int> Q;
Q.push(s);
vis[s]=1;
ord.push_back(s);
while(!Q.empty()){
int cur=Q.front(); Q.pop();
for(int v : t[cur]){
if(vis[v]==0){
vis[v]=1;
Q.push(v);
ord.push_back(v);
}
}
}
return ord.back();
}
int dfs_h(int par, int cur){
if((int)t[cur].size()==1 and t[cur][0]==par){
return height[cur]=1;
}
int ret=1;
for(int v : t[cur]){
if(v!=par){
ret=max(ret,dfs_h(cur,v)+1);
}
}
return height[cur]=ret;
}
void makesum(vector<vector<LL>> &vec){
for(int i=0; i<(int)vec.size(); ++i){
for(int j=1; j<(int)vec.size(); ++j){
vec[i][j]+=vec[i][j-1];
if(vec[i][j]>MOD)vec[i][j]-=MOD;
}
}
for(int j=0; j<(int)vec.size(); ++j){
for(int i=1; i<(int)vec.size(); ++i){
vec[i][j]+=vec[i-1][j];
if(vec[i][j]>MOD)vec[i][j]-=MOD;
}
}
}
inline LL modcomb(int a, int b){
return (fac[a]*inv[b]%MOD)*inv[a-b]%MOD;
}
LL getp(vector<vector<LL>> &vec, int i, int j){
LL gp=vec[i][j];
if(i>0)gp-=vec[i-1][j];
if(j>0)gp-=vec[i][j-1];
if(i>0 and j>0)gp+=vec[i-1][j-1];
return (gp+MOD+MOD)%MOD;
}
vector<vector<LL>> dp(int par, int cur, int s=1){
int sz= min(height[cur]+s+1,D+1);
if((int)t[cur].size()==1 and t[cur][0]!=par){
return dp(cur,t[cur][0]);
}
if((int)t[cur].size()==2){
for(int v: t[cur]){
if(v!= par) return dp(cur,v,s+1);
}
}
vector<vector<LL>> ret (sz,vector<LL>(sz));
ret[0][0]=1;
for(auto v : t[cur]){
if(v!= par){
makesum(ret);
vector<vector<LL>> tmp (sz,vector<LL>(sz));
auto res = dp(cur, v);
for(int i=0; i<(int)tmp.size();++i){
for(int j=0; j<(int)tmp.size(); ++j){
if(i>j){
tmp[i][j]=tmp[j][i];
continue;
}
if(i<(int)res.size() && j< (int)res.size()){
int ii=min({i,D-j}),jj=min({j,D-i});
LL gp=getp(res,i,j);
tmp[i][j]+=gp*ret[ii][jj];
if(i+j<=D)tmp[i][j]-=gp*getp(ret,i,j);
}
{
int ii=min({i,(int)res.size()-1,D-j}),jj=min({j,(int)res.size()-1,D-i});
LL gp=getp(ret,i,j);
if(ii>=0 and jj>=0)tmp[i][j]+=gp*res[ii][jj];
}
if(i+j<=D){
int ii=min(i-1,(int)res.size()-1);
int jj=min(j-1,(int)res.size()-1);
if(j<(int)res.size()and i>0 and j>0)tmp[i][j]+=((ret[i][j-1]-ret[i-1][j-1]+MOD)%MOD)*((res[ii][j]-res[ii][j-1]+MOD)%MOD);
if(i<(int)res.size()and i>0 and j>0)tmp[i][j]+=((ret[i-1][j]-ret[i-1][j-1]+MOD)%MOD)*((res[i][jj]-res[i-1][jj]+MOD)%MOD);
}
tmp[i][j]=(tmp[i][j]%MOD+MOD)%MOD;
}
}
ret=move(tmp);
}
}
vector<vector<LL>> res (sz,vector<LL>(sz));
for(int i=0; i<(int)ret.size(); ++i){
for(int j=0; j<(int)ret.size(); ++j){
if(i+j>=height[cur]-1)for(int k=max(0,j+s-sz+1); k<min(s+1,sz-i); ++k){
res[i+k][j+s-k]+=ret[i][j]*modcomb(s,k);
res[i+k][j+s-k]=res[i+k][j+s-k]%MOD;
}
}
}
makesum(res);
return res;
}
long long modpow(long long a, long long n,long long mod=MOD){
long long i=1,ret=1,p=a;
while(i<=n){
if(i&n) ret=(ret*p)%mod;
i=(i<<1);
p=(p*p)%mod;
}
return ret;
}
void solve(){
for(int i=0; i<n-1; ++i){
int a,b;
cin >> a >>b;
--a;--b;
t[a].push_back(b);
t[b].push_back(a);
}
fac[0]=1;
for(int i=1; i<(int)fac.size(); ++i){
fac[i]=fac[i-1]*i%MOD;
}
inv.back()=modpow(fac.back(),MOD-2);
for(int i=(int)fac.size()-2; i>=0; --i){
inv[i]=inv[i+1]*(i+1)%MOD;
}
int root=bfs(0);
root=bfs(root);
maxd = dfs_h(-1,root);
D=(maxd)/2;
auto ans=dp(-1,root);
cout << ans[D][D]<<"\n";
}
};
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
long long n=0;
cin >> n;
Problem p(n);
p.solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Oriented Tree |
User |
Hoi_koro |
Language |
C++14 (GCC 5.4.1) |
Score |
1800 |
Code Size |
5773 Byte |
Status |
AC |
Exec Time |
962 ms |
Memory |
252524 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1800 / 1800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
1 ms |
256 KB |
0_01.txt |
AC |
1 ms |
256 KB |
0_02.txt |
AC |
1 ms |
256 KB |
0_03.txt |
AC |
1 ms |
256 KB |
1_00.txt |
AC |
1 ms |
256 KB |
1_01.txt |
AC |
5 ms |
4608 KB |
1_02.txt |
AC |
5 ms |
4736 KB |
1_03.txt |
AC |
2 ms |
384 KB |
1_04.txt |
AC |
2 ms |
384 KB |
1_05.txt |
AC |
4 ms |
512 KB |
1_06.txt |
AC |
5 ms |
640 KB |
1_07.txt |
AC |
5 ms |
640 KB |
1_08.txt |
AC |
6 ms |
768 KB |
1_09.txt |
AC |
11 ms |
1744 KB |
1_10.txt |
AC |
24 ms |
5532 KB |
1_11.txt |
AC |
48 ms |
12476 KB |
1_12.txt |
AC |
101 ms |
24764 KB |
1_13.txt |
AC |
309 ms |
75532 KB |
1_14.txt |
AC |
962 ms |
252524 KB |
1_15.txt |
AC |
414 ms |
77056 KB |
1_16.txt |
AC |
511 ms |
89600 KB |
1_17.txt |
AC |
3 ms |
384 KB |
1_18.txt |
AC |
3 ms |
384 KB |
1_19.txt |
AC |
3 ms |
384 KB |
1_20.txt |
AC |
3 ms |
384 KB |
1_21.txt |
AC |
3 ms |
384 KB |
1_22.txt |
AC |
2 ms |
384 KB |
1_23.txt |
AC |
2 ms |
384 KB |
1_24.txt |
AC |
2 ms |
384 KB |
1_25.txt |
AC |
2 ms |
384 KB |
1_26.txt |
AC |
2 ms |
384 KB |
1_27.txt |
AC |
2 ms |
384 KB |
1_28.txt |
AC |
2 ms |
384 KB |