QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#438934#7677. Easy Diameter ProblemGraygooML 0ms0kbC++143.2kb2024-06-11 12:06:592024-06-11 12:07:01

Judging History

你现在查看的是最新测评结果

  • [2024-06-11 12:07:01]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-06-11 12:06:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define int long long
const int mod = 1000000007;
vector<int> to[505];
int dd[305][2][305];
int tmp[305][305];
int ff[305];
int dep[305];
int n;
unordered_map<int,int> mp[305][305][305];
void dfs1(int x,int fa){
    ff[x]=fa;
    for(auto v:to[x]){
        if(v==fa)continue;
        dfs1(v,x);
    }
    return ;
}
void dfs2(int x,int fa){
    tmp[x][0]=1;
    for(auto v:to[x]){
        if(v==fa)continue;
        dfs2(v,x);
        for(int i=0;i<=n;i++)tmp[x][i+1]+=tmp[v][i];
    }
    return ;
}
int C[305][305];
int fac[305];
int solve(int x,int y,int k,int p){//x 这个子树或边 直径为y 除了k这个子树都有p的前置
    if(mp[y][k][p].count(x))return mp[y][k][p][x];
    int ans=0;
    if(y==0)return mp[y][k][p][x]=1;
    if(x>n){
        int a=x-n;
        int b=ff[a];
        int c=dd[a][0][(y-1)/2];
        int d=dd[a][1][(y-1)/2];
        if(k!=a){
            for(int i=0;i<c;i++)ans=(ans+(i==0?1:C[i+p-1][i])*fac[c]%mod*solve(b,y-1,a,c-i))%mod;
            ans=(ans+fac[d]*solve(a,y-1,b,p+d))%mod;
        }else{
            ans=(ans+fac[c]*solve(b,y-1,a,p+c))%mod;
            for(int i=0;i<d;i++)ans=(ans+(i==0?1:C[i+p-1][i])*fac[d]%mod*solve(a,y-1,b,d-i))%mod;
        }
    }else{
        auto calc=[&](int o){
            return o==ff[x]?dd[x][1][y/2-1]:dd[o][0][y/2-1];
        };
        int tot=0;
        for(auto v:to[x])tot+=calc(v);
        for(auto v:to[x]){
            int u=calc(v);
            if(!u)continue;
            int tar=v==ff[x]?x:v;tar+=n;
            int cur=tot-u;
            if(v==k){
                for(int i=0;i<cur;i++)ans=(ans+(i==0?1:C[i+p-1][i])*fac[cur]%mod*solve(tar,y-1,x,cur-i))%mod;
            }else{
                int oo=calc(k);
                int cc=cur-oo;
                int qq=solve(tar,y-1,x,cur+p);
                for(int i=0;i<=cc;i++){
                    if(cc-i+oo==0)continue;
                    ans=(ans+(i==0?1:C[i+p-1][i])*C[cc-i+oo][oo]%mod*fac[oo]%mod*fac[cc]%mod*qq)%mod;
                }
            }
        }
    }
    return mp[y][k][p][x]=ans;
}
void dfs3(int x,int fa){
    dep[x]=dep[fa]+1;
    for(auto v:to[x]){
        if(v==fa)continue;
        dfs3(v,x);
    }
    return ;
}
signed main(){
    //freopen("tree5.in","r",stdin);
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        to[u].push_back(v);
        to[v].push_back(u);
    }
    dfs1(1,0);
    for(int i=2;i<=n;i++){
        memset(tmp,0,sizeof(tmp));
        dfs2(i,ff[i]);
        for(int j=0;j<=n;j++)dd[i][0][j]=tmp[i][j];
        memset(tmp,0,sizeof(tmp));
        dfs2(ff[i],i);
        for(int j=0;j<=n;j++)dd[i][1][j]=tmp[ff[i]][j];
    }
    for(int i=0;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    dfs3(1,0);
    int x=max_element(dep+1,dep+n+1)-dep;
    dfs3(x,0);
    int y=max_element(dep+1,dep+n+1)-dep;
    dfs1(x,0);
    int t=y;
    for(int i=1;i<=dep[y]/2;i++)t=ff[t];
    int c=dep[y]%2==1?t:n+t;
    dfs1(1,0);
    cout<<solve(c,dep[y]-1,0,0)<<endl;
    return 0;
}

詳細信息

Test #1:

score: 0
Memory Limit Exceeded

input:

3
1 2
3 2

output:

4

result: