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
Submission Time |
|
Task |
D - Oriented Tree |
User |
WA_TLE |
Language |
C++14 (GCC 5.4.1) |
Score |
1800 |
Code Size |
5024 Byte |
Status |
AC |
Exec Time |
22 ms |
Memory |
8192 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 |
22 ms |
8192 KB |
1_02.txt |
AC |
22 ms |
8192 KB |
1_03.txt |
AC |
10 ms |
384 KB |
1_04.txt |
AC |
13 ms |
384 KB |
1_05.txt |
AC |
5 ms |
640 KB |
1_06.txt |
AC |
6 ms |
768 KB |
1_07.txt |
AC |
6 ms |
768 KB |
1_08.txt |
AC |
6 ms |
896 KB |
1_09.txt |
AC |
7 ms |
1152 KB |
1_10.txt |
AC |
8 ms |
1536 KB |
1_11.txt |
AC |
10 ms |
1920 KB |
1_12.txt |
AC |
12 ms |
2688 KB |
1_13.txt |
AC |
15 ms |
4224 KB |
1_14.txt |
AC |
16 ms |
5504 KB |
1_15.txt |
AC |
19 ms |
7040 KB |
1_16.txt |
AC |
21 ms |
7936 KB |
1_17.txt |
AC |
5 ms |
512 KB |
1_18.txt |
AC |
7 ms |
512 KB |
1_19.txt |
AC |
5 ms |
512 KB |
1_20.txt |
AC |
5 ms |
512 KB |
1_21.txt |
AC |
4 ms |
512 KB |
1_22.txt |
AC |
6 ms |
384 KB |
1_23.txt |
AC |
6 ms |
384 KB |
1_24.txt |
AC |
7 ms |
384 KB |
1_25.txt |
AC |
8 ms |
384 KB |
1_26.txt |
AC |
10 ms |
384 KB |
1_27.txt |
AC |
10 ms |
384 KB |
1_28.txt |
AC |
14 ms |
384 KB |