QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#881901 | #10017. Experiments With Divine Trees | rotcar07 | WA | 14ms | 13836kb | C++23 | 1.2kb | 2025-02-04 19:35:03 | 2025-02-04 19:35:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998244353,N=1e5+5;
int n;vector<int> e[N];
int sz[N],cnt[N],val[N],tot[N];bool sb[N];
void dfs(int p,int f){
sz[p]=1,cnt[p]=(e[p].size()==1);
for(int x:e[p])if(x!=f) dfs(x,p),sz[p]+=sz[x],cnt[p]+=cnt[x];
tot[min(sz[p],n-sz[p])]++;
if(e[p].size()<=2) sb[n-sz[p]]=1;
if(e[f].size()<=2) sb[sz[p]]=1;
val[min(n-sz[p],sz[p])]=cnt[p];
}
inline int qpow(int a,int b){
int ans=1;
while(b){
if(b&1) ans=ans*1ll*a%mod;
a=a*1ll*a%mod,b>>=1;
}
return ans;
}
int fac[N],inv[N];
inline int C(int n,int m){if(n<m||m<0)return 0;return fac[n]*1ll*inv[m]%mod*inv[n-m]%mod;}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1,u,v;i<n;i++) cin>>u>>v,e[u].emplace_back(v),e[v].emplace_back(u);
for(int i=fac[0]=1;i<=n;i++) fac[i]=fac[i-1]*1ll*i%mod;
inv[n]=qpow(fac[n],mod-2);
for(int i=n;i>=1;i--) inv[i-1]=inv[i]*1ll*i%mod;
dfs(1,0);
long long ans=2;
for(int i=1;i<=n/2;i++)if(tot[i]){
bool f=(tot[i]>1||tot[i-1]||sb[i]);
ans+=(f?C(n,i):C(n,i)+mod-C(n-cnt[1],n-i-val[i]))*(i*2==n?1:2);
}
cout<<ans%mod<<'\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
3 1 3 3 2
output:
8
result:
ok answer is '8'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
4 1 2 2 3 2 4
output:
10
result:
ok answer is '10'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5864kb
input:
7 1 2 1 4 1 5 1 6 2 3 2 7
output:
84
result:
ok answer is '84'
Test #4:
score: -100
Wrong Answer
time: 14ms
memory: 13836kb
input:
100000 1 2 3 4 2 4 5 6 4 6 7 8 6 8 9 10 8 10 10 11 11 12 13 14 12 14 15 16 14 16 17 18 16 18 19 20 18 20 21 22 20 22 22 23 23 24 25 26 24 26 27 28 26 28 29 30 28 30 31 32 30 32 33 34 32 34 35 36 34 36 37 38 36 38 39 40 38 40 40 41 41 42 43 44 42 44 45 46 44 46 47 48 46 48 48 49 49 50 51 52 50 52 53 ...
output:
887431311
result:
wrong answer expected '417443307', found '887431311'