QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#438934 | #7677. Easy Diameter Problem | Graygoo | ML | 0ms | 0kb | C++14 | 3.2kb | 2024-06-11 12:06:59 | 2024-06-11 12:07:01 |
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