Submission #2374635


Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}


const int mod=1000000007;
inline void add(int &a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}
int mpow(int n,int m){
    int ret=1;
    while(m){
        if(m&1)ret=ret*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ret;
}
const int FACT_SIZE=1111111;
int fact[FACT_SIZE];
int inv[FACT_SIZE];
struct fact_exec{
    fact_exec(){
        fact[0]=1;
        for(int i=1;i<FACT_SIZE;i++)fact[i]=fact[i-1]*i%mod;
        inv[FACT_SIZE-1]=mpow(fact[FACT_SIZE-1],mod-2);
        for(int i=FACT_SIZE-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    }
}factexec;
int nCk(int n,int k){
    if(n<0|k<0||k>n)return 0;
    return fact[n]*inv[k]%mod*inv[n-k]%mod;
}
int nPk(int n,int k){
    if(n<0||k<0||k>n)return 0;
    return fact[n]*inv[n-k]%mod;
}


int N;
vint G[1111];

int dist[1111];

void dfs(int v,int p,int d){
    dist[v]=d;
    for(auto u:G[v]){
        if(u==p)continue;
        dfs(u,v,d+1);
    }
}


int D;
int X;
int dp[1111][1111];
void dfs2(int v,int p,int d){
    rep(i,D/2+1)dp[v][i]=1;
    for(auto u:G[v]){
        if(u==p)continue;
        dfs2(u,v,d+1);
        rep(i,D/2+1)dp[v][i]=dp[v][i]*(dp[u][i]+dp[u][i+1])%mod;
    }
    rep(i,D/2+1)if(i>X||d-i>D/2-X)dp[v][i]=0;
}
void solve(int c){
    int ans=0;
    for(X=0;X<=D/2;X++){
        memset(dp,0,sizeof(dp));
        dfs2(c,-1,0);
        add(ans,dp[c][0]);
    }
    cout<<ans<<endl;
}

signed main(){


    cin>>N;
    rep(i,N-1){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].pb(b);G[b].pb(a);
    }

    dfs(0,-1,0);
    int v=0;
    rep(i,N)if(dist[i]>dist[v])v=i;
    dfs(v,-1,0);

    int u=0;
    rep(i,N)if(dist[i]>dist[u])u=i;

    vint latte(N);
    rep(i,N)latte[i]=dist[i];
    dfs(u,-1,0);
    rep(i,N)chmax(latte[i],dist[i]);

    vint lis;
    rep(i,N)if(latte[i]<=(dist[v]+1)/2)lis.pb(i);

    D=dist[v];

    if(lis.size()==1){
       solve(lis[0]);
    }
    else{
        int u=lis[0],v=lis[1];

        vint x(N),y(N),z(N),w(N);

        for(X=0;X<=D/2;X++){
            memset(dp,0,sizeof(dp));
            dfs2(u,v,0);
            x[X]=dp[u][0];

           // memset(dp,0,sizeof(dp));
           // dfs2(v,u,0);
            y[X]=dp[v][0];
        }


        D++;
        for(X=0;X<=D/2;X++){
            memset(dp,0,sizeof(dp));
            dfs2(u,v,0);
            z[X]=dp[u][0];

            memset(dp,0,sizeof(dp));
            dfs2(v,u,0);
            w[X]=dp[v][0];
        }

        D--;
        z[0]=w[0]=0;
        for(int i=1;i<N;i++)z[i]=(z[i]-x[i]-x[i-1]+mod*2)%mod;
        for(int i=1;i<N;i++)w[i]=(w[i]-y[i]-y[i-1]+mod*2)%mod;

        int ans=0;
        for(int i=0;i<=D/2;i++){
            for(int j=0;j<=D/2;j++){
                int a=i;
                int b=D/2-i;
                int c=j;
                int d=D/2-j;
                if(a+d<=D/2+1&&b+c+1<=D/2+1)add(ans,x[i]*y[j]%mod);
                if(a+d+1<=D/2+1&&b+c<=D/2+1)add(ans,x[i]*y[j]%mod);
            }
        }

        for(int i=0;i<=D/2;i++){
            for(int j=0;j<=D/2+1;j++){
                int a=i;
                int b=D/2-i;
                int c=j;
                int d=D/2+1-j;
                if(a+d<=D/2+1&&b+c+1<=D/2+1)add(ans,x[i]*w[j]%mod);
                if(a+d+1<=D/2+1&&b+c<=D/2+1)add(ans,x[i]*w[j]%mod);
            }
        }

        for(int i=0;i<=D/2+1;i++){
            for(int j=0;j<=D/2+1;j++){
                int a=i;
                int b=D/2+1-i;
                int c=j;
                int d=D/2+1-j;
                if(a+d<=D/2+1&&b+c+1<=D/2+1)add(ans,z[i]*w[j]%mod);
                if(a+d+1<=D/2+1&&b+c<=D/2+1)add(ans,z[i]*w[j]%mod);
            }
        }


        for(int i=0;i<=D/2+1;i++){
            for(int j=0;j<=D/2;j++){
                int a=i;
                int b=D/2+1-i;
                int c=j;
                int d=D/2-j;
                if(a+d<=D/2+1&&b+c+1<=D/2+1)add(ans,z[i]*y[j]%mod);
                if(a+d+1<=D/2+1&&b+c<=D/2+1)add(ans,z[i]*y[j]%mod);
            }
        }


        cout<<ans<<endl;
    }
    return 0;
}

Submission Info

Submission Time
Task D - Oriented Tree
User latte0119
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4633 Byte
Status WA
Exec Time 2068 ms
Memory 27392 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1800
Status
AC × 2
WA × 2
AC × 22
WA × 10
TLE × 1
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 20 ms 27264 KB
0_01.txt WA 23 ms 27264 KB
0_02.txt WA 23 ms 27264 KB
0_03.txt AC 21 ms 27264 KB
1_00.txt WA 22 ms 27264 KB
1_01.txt AC 1135 ms 27392 KB
1_02.txt TLE 2068 ms 27392 KB
1_03.txt AC 20 ms 27392 KB
1_04.txt WA 23 ms 27392 KB
1_05.txt AC 29 ms 27264 KB
1_06.txt WA 53 ms 27392 KB
1_07.txt AC 36 ms 27264 KB
1_08.txt WA 69 ms 27392 KB
1_09.txt WA 99 ms 27392 KB
1_10.txt AC 76 ms 27264 KB
1_11.txt WA 236 ms 27392 KB
1_12.txt AC 185 ms 27392 KB
1_13.txt WA 745 ms 27392 KB
1_14.txt AC 569 ms 27392 KB
1_15.txt AC 866 ms 27392 KB
1_16.txt AC 1075 ms 27392 KB
1_17.txt AC 25 ms 27264 KB
1_18.txt AC 24 ms 27264 KB
1_19.txt AC 23 ms 27392 KB
1_20.txt WA 28 ms 27392 KB
1_21.txt AC 22 ms 27392 KB
1_22.txt AC 22 ms 27392 KB
1_23.txt AC 22 ms 27392 KB
1_24.txt AC 21 ms 27392 KB
1_25.txt AC 21 ms 27264 KB
1_26.txt AC 21 ms 27392 KB
1_27.txt AC 21 ms 27392 KB
1_28.txt AC 21 ms 27392 KB