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