QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#717113#7509. 01treefzxTL 79ms61636kbC++142.5kb2024-11-06 16:57:192024-11-06 16:57:21

Judging History

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

  • [2024-11-06 16:57:21]
  • 评测
  • 测评结果:TL
  • 用时:79ms
  • 内存:61636kb
  • [2024-11-06 16:57:19]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long 
#define pb push_back
using namespace std;
const int Mod=1e9+7;
const int INF=1e6+5;
int n,col[INF],fav[INF],ifav[INF];string s,t;
vector <int> e[INF];
int ksm(int x,int y) {
    int ba=x%Mod,ans=1;
    while (y) {
        if (y&1) ans=(ans*ba)%Mod;
        ba=(ba*ba)%Mod;y>>=1;
    }
    return ans;
}
void init() {
    fav[0]=1;int N=1e6;
    for (int i=1;i<=N;i++) fav[i]=fav[i-1]*i%Mod;
    ifav[N]=ksm(fav[N],Mod-2);
    for (int i=N-1;~i;i--) ifav[i]=ifav[i+1]*(i+1)%Mod;
}
int C(int x,int y) {
    if (x<y) return 0;
    return fav[x]*ifav[y]%Mod*ifav[x-y]%Mod;
}
void DFS(int x,int fa) {
    for (int v:e[x]) {
        if (v==fa) continue;
        col[v]=col[x]^1;
        DFS(v,x);
    }
}
int A[5],B[5];
int sz1[INF][5],sz2[INF][5],res;
int X,Y,Z;
void DFS2(int x,int fa) {
    for (int w=0;w<3;w++) sz1[x][w]=sz2[x][w]=0;
    if (s[x]=='?') sz1[x][0]++;
    else if (s[x]=='0') sz1[x][1]++;
    else sz1[x][2]++;

    if (t[x]=='?') sz2[x][0]++;
    else if (t[x]=='0') sz2[x][1]++;
    else sz2[x][2]++;
    for (int v:e[x]) {
        if (v==fa) continue;
        DFS2(v,x);
        // W<=B[1]-A[1]+T2
        // B[1]-A[1]-T1
        for (int W=0ll;W<=min(Y,sz1[v][0]+sz2[v][0]);W++) {
            res+=C(sz1[v][0]+sz2[v][0],W)%Mod
                *C(Z-sz2[v][0]-sz1[v][0],Y-W)%Mod*abs(sz1[v][0]-W+sz1[v][1]-sz2[v][1]);
            res%=Mod;
        }

        for (int i=0;i<3;i++)
            sz1[x][i]+=sz1[v][i],
            sz2[x][i]+=sz2[v][i];
    }
}
void solve() {
    for (int w=0;w<=n+3;w++) e[w].clear();
    cin>>n;res=0;
    for (int i=1;i<n;i++) {
        int x=0,y=0;
        cin>>x>>y;
        e[x].pb(y);
        e[y].pb(x);
    }
    for (int w=0;w<3;w++) A[w]=B[w]=0;
    DFS(1,0);cin>>s>>t;s=" "+s;t=" "+t;
    for (int i=1;i<=n;i++) {
        if (s[i]=='?') {A[0]++;continue;}
        if (col[i]==1) {
            if (s[i]=='0') s[i]='1';
            else s[i]='0';
        }
        if (s[i]=='0') A[1]++;
        else A[2]++;
    }
    for (int i=1;i<=n;i++) {
        if (t[i]=='?') {B[0]++;continue;}
        if (col[i]==1) {
            if (t[i]=='0') t[i]='1';
            else t[i]='0';
        }
        if (t[i]=='0') B[1]++;
        else B[2]++;
    }
    X=-B[1]+A[1]-B[0];
    Y=-B[1]+A[1]+A[0];
    Z=A[0]+B[0];
    DFS2(1,0);
    cout<<res<<"\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    int t=0;cin>>t;init();
    while (t--) solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 14ms
memory: 48612kb

input:

3
2
1 2
00
11
3
1 2
2 3
???
???
3
1 2
2 3
??1
0?0

output:

1
16
1

result:

ok 3 number(s): "1 16 1"

Test #2:

score: 0
Accepted
time: 15ms
memory: 46628kb

input:

1000
23
1 2
1 3
1 4
2 5
5 6
4 7
3 8
4 9
8 10
8 11
8 12
1 13
7 14
10 15
7 16
7 17
5 18
18 19
12 20
9 21
21 22
6 23
00?10?0000??1?00111?010
011??1?10?01?110?0??101
6
1 2
1 3
1 4
4 5
3 6
000?10
1???01
25
1 2
2 3
2 4
4 5
5 6
2 7
4 8
5 9
7 10
8 11
11 12
5 13
11 14
3 15
6 16
14 17
1 18
4 19
6 20
4 21
5 22...

output:

53545
24
11724
2228
162
14
711
28
550
1680
52
2
13
988
9480
2342
626416
0
71780
1
88
39207
19448
4
37395
9602
3253496
38057200
1066
3
303732
1608
281022
11718
170
78
15
1219376
29364
9092
7
0
2
7014
1942448
170371
75845
167217
16554
64
904
564290
14822
1127090
1758504
1227646
14833316
14954550
36055...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 11ms
memory: 46868kb

input:

1
3000
1 2
2 3
2 4
1 5
3 6
2 7
5 8
8 9
9 10
10 11
2 12
11 13
7 14
11 15
7 16
13 17
8 18
1 19
11 20
10 21
18 22
7 23
7 24
15 25
23 26
24 27
14 28
15 29
25 30
16 31
6 32
10 33
3 34
30 35
16 36
9 37
36 38
28 39
26 40
33 41
1 42
11 43
20 44
23 45
14 46
31 47
41 48
11 49
48 50
45 51
6 52
10 53
32 54
38 5...

output:

924036898

result:

ok 1 number(s): "924036898"

Test #4:

score: 0
Accepted
time: 12ms
memory: 46844kb

input:

1
3000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

429465738

result:

ok 1 number(s): "429465738"

Test #5:

score: 0
Accepted
time: 25ms
memory: 47544kb

input:

1
3000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 5...

output:

650625747

result:

ok 1 number(s): "650625747"

Test #6:

score: 0
Accepted
time: 79ms
memory: 60360kb

input:

1
100000
1 2
1 3
3 4
1 5
2 6
6 7
2 8
1 9
6 10
1 11
3 12
11 13
5 14
9 15
12 16
6 17
13 18
13 19
14 20
7 21
14 22
21 23
12 24
17 25
14 26
3 27
4 28
8 29
22 30
12 31
6 32
30 33
4 34
15 35
12 36
3 37
20 38
7 39
37 40
5 41
13 42
34 43
9 44
27 45
39 46
43 47
3 48
17 49
36 50
12 51
1 52
45 53
35 54
15 55
2...

output:

143309878

result:

ok 1 number(s): "143309878"

Test #7:

score: 0
Accepted
time: 62ms
memory: 61636kb

input:

1
100000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54...

output:

724432513

result:

ok 1 number(s): "724432513"

Test #8:

score: -100
Time Limit Exceeded

input:

1
100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52...

output:


result: