Submission #2151137
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n;
vector<int>edge[1005];
P DFS(int v,int u,int d){
P ret = mp(d,v);
rep(i,edge[v].size()){
if(edge[v][i]==u) continue;
ret=max(ret,DFS(edge[v][i],v,d+1));
}
return ret;
}
int dist[1005][2];
void DFS2(int v,int u,int d,int ty){
dist[v][ty] = d;
rep(i,edge[v].size()){
if(edge[v][i]==u) continue;
DFS2(edge[v][i],v,d+1,ty);
}
}
int must,u,v;
bool ok(int x,int val){
int D = dist[x][0];
if( (D+abs(val))/2 > (dist[v][0]+1)/2 ) return false;
D = dist[x][1];
if( (D+abs(val-must))/2 > (dist[v][0]+1)/2 ) return false;
return true;
}
ll dp[1005][2005];
ll dfs(int x,int y,int val){
if(x == v){
if(must == val) return 1LL;
else return 0LL;
}
if(dp[x][val+1050]>=0) return dp[x][val+1050];
ll ret = 1;
rep(i,edge[x].size()){
if(edge[x][i] == y) continue;
ll add = 0;
if(ok(edge[x][i],val+1)){
add += dfs(edge[x][i],x,val+1);
}
if(ok(edge[x][i],val-1)){
add += dfs(edge[x][i],x,val-1);
}
add %= mod;
ret = ret*add%mod;
}
return dp[x][val+1050]=ret;
}
int ok2(int x,int val){
int D = dist[x][0];
if( (D+abs(val))/2 > (dist[v][0]+1)/2 ) return -1;
D = dist[x][1];
if( (D+abs(val-must))/2 > (dist[v][0]+1)/2 ) return -1;
if(dist[x][0] < dist[x][1]){
int dif = dist[v][0]-dist[x][1];
if(dif<abs(val)) return 1;
}
else{
int dif = dist[v][0]-dist[x][0];
if(dif<abs(val-must)) return 2;
}
return 0;
}
ll dp2[1005][2005][4];
void dfs2(int x,int y,int val){
if(x == v){
rep(a,4)dp2[x][val+1050][a] = 0;
if(must == val) dp2[x][val+1050][0] = 1LL;
return ;
}
if(dp2[x][val+1050][0]>=0) return ;
rep(a,4)dp2[x][val+1050][a] = 0;
ll ret[2][4]={};
ret[0][ok2(x,val)] = 1LL;
int cur = 0,nxt = 1;
rep(i,edge[x].size()){
if(edge[x][i] == y) continue;
rep(a,4) ret[nxt][a] = 0;
if(ok2(edge[x][i],val+1) != -1){
dfs2(edge[x][i],x,val+1);
rep(a,4)rep(b,4) ret[nxt][a|b] += ret[cur][a]*dp2[edge[x][i]][val+1+1050][b]%mod;
}
if(ok2(edge[x][i],val-1) != -1){
dfs2(edge[x][i],x,val-1);
rep(a,4)rep(b,4) ret[nxt][a|b] += ret[cur][a]*dp2[edge[x][i]][val-1+1050][b]%mod;
}
rep(a,4) ret[nxt][a] %= mod;
swap(cur,nxt);
}
rep(a,4)dp2[x][val+1050][a] = ret[cur][a];
return ;
}
int main(){
cin>>n;
rep(i,n-1){
int a,b; cin>>a>>b;
edge[a].pb(b);
edge[b].pb(a);
}
P p = DFS(1,-1,0);
P q = DFS(p.sc,-1,0);
u = p.sc, v = q.sc;
DFS2(u,-1,0,0);
DFS2(v,-1,0,1);
if(q.fi%2 == 0){
memset(dp,-1LL,sizeof(dp));
must = 0;
cout << dfs(u,-1,0) << endl;
}
else{
ll ans = 0;
memset(dp2,-1LL,sizeof(dp2));
must = 1;
dfs2(u,-1,0);
for(int i=0;i<3;i++) ans += dp2[u][1050][i];
memset(dp2,-1LL,sizeof(dp2));
must = -1;
dfs2(u,-1,0);
for(int i=0;i<3;i++) ans += dp2[u][1050][i];
cout << ans%mod << endl;
}
}
Submission Info
Submission Time |
|
Task |
D - Oriented Tree |
User |
IH19980412 |
Language |
C++14 (GCC 5.4.1) |
Score |
1800 |
Code Size |
3434 Byte |
Status |
AC |
Exec Time |
121 ms |
Memory |
64000 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 |
5 ms |
17536 KB |
0_01.txt |
AC |
25 ms |
63744 KB |
0_02.txt |
AC |
25 ms |
63744 KB |
0_03.txt |
AC |
5 ms |
17536 KB |
1_00.txt |
AC |
24 ms |
63744 KB |
1_01.txt |
AC |
14 ms |
17664 KB |
1_02.txt |
AC |
121 ms |
64000 KB |
1_03.txt |
AC |
6 ms |
17536 KB |
1_04.txt |
AC |
26 ms |
63744 KB |
1_05.txt |
AC |
7 ms |
17536 KB |
1_06.txt |
AC |
29 ms |
63744 KB |
1_07.txt |
AC |
7 ms |
17536 KB |
1_08.txt |
AC |
31 ms |
63744 KB |
1_09.txt |
AC |
34 ms |
63744 KB |
1_10.txt |
AC |
7 ms |
17664 KB |
1_11.txt |
AC |
41 ms |
63872 KB |
1_12.txt |
AC |
8 ms |
17664 KB |
1_13.txt |
AC |
66 ms |
63872 KB |
1_14.txt |
AC |
11 ms |
17664 KB |
1_15.txt |
AC |
12 ms |
17664 KB |
1_16.txt |
AC |
14 ms |
17664 KB |
1_17.txt |
AC |
7 ms |
17536 KB |
1_18.txt |
AC |
6 ms |
17536 KB |
1_19.txt |
AC |
6 ms |
17536 KB |
1_20.txt |
AC |
26 ms |
63744 KB |
1_21.txt |
AC |
6 ms |
17536 KB |
1_22.txt |
AC |
6 ms |
17536 KB |
1_23.txt |
AC |
6 ms |
17536 KB |
1_24.txt |
AC |
6 ms |
17536 KB |
1_25.txt |
AC |
6 ms |
17536 KB |
1_26.txt |
AC |
6 ms |
17536 KB |
1_27.txt |
AC |
6 ms |
17536 KB |
1_28.txt |
AC |
6 ms |
17536 KB |