Submission #2375087


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){

    int l=max(0ll,X+d-D/2);

    for(int i=l;i<=X;i++)dp[v][i]=1;
    for(auto u:G[v]){
        if(u==p)continue;
        dfs2(u,v,d+1);
        for(int i=l;i<=X;i++)dp[v][i]=dp[v][i]*(dp[u][i]+dp[u][i+1])%mod;
    }
}
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 1800
Code Size 4635 Byte
Status AC
Exec Time 1439 ms
Memory 27392 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1800 / 1800
Status
AC × 4
AC × 33
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 AC 23 ms 27264 KB
0_02.txt AC 23 ms 27264 KB
0_03.txt AC 21 ms 27264 KB
1_00.txt AC 22 ms 27264 KB
1_01.txt AC 493 ms 27392 KB
1_02.txt AC 1439 ms 27392 KB
1_03.txt AC 20 ms 27264 KB
1_04.txt AC 24 ms 27392 KB
1_05.txt AC 27 ms 27264 KB
1_06.txt AC 62 ms 27392 KB
1_07.txt AC 33 ms 27264 KB
1_08.txt AC 78 ms 27392 KB
1_09.txt AC 114 ms 27392 KB
1_10.txt AC 60 ms 27264 KB
1_11.txt AC 230 ms 27392 KB
1_12.txt AC 117 ms 27392 KB
1_13.txt AC 601 ms 27392 KB
1_14.txt AC 282 ms 27392 KB
1_15.txt AC 392 ms 27392 KB
1_16.txt AC 468 ms 27392 KB
1_17.txt AC 24 ms 27392 KB
1_18.txt AC 24 ms 27264 KB
1_19.txt AC 23 ms 27392 KB
1_20.txt AC 30 ms 27392 KB
1_21.txt AC 22 ms 27392 KB
1_22.txt AC 21 ms 27392 KB
1_23.txt AC 21 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 27264 KB
1_28.txt AC 21 ms 27392 KB