QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#881910#10017. Experiments With Divine Treesrotcar07WA 10ms13568kbC++231.2kb2025-02-04 19:43:202025-02-04 19:43:20

Judging History

This is the latest submission verdict.

  • [2025-02-04 19:43:20]
  • Judged
  • Verdict: WA
  • Time: 10ms
  • Memory: 13568kb
  • [2025-02-04 19:43:20]
  • Submitted

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[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]||i*2==n);
        ans+=(f?C(n,i):C(n,i)+mod-C(n-cnt[1],n-i-(val[i]?:cnt[1]-val[n-i])))*(i*2==n?1:2);
    }
    cout<<ans%mod<<'\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3840kb

input:

3
1 3
3 2

output:

8

result:

ok answer is '8'

Test #2:

score: 0
Accepted
time: 0ms
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: 3584kb

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: 10ms
memory: 13568kb

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:

-505223319

result:

wrong answer expected '417443307', found '-505223319'