QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#698441#6757. 深搜Zaunese100 ✓1710ms161380kbC++147.6kb2024-11-01 19:41:172024-11-01 19:41:18

Judging History

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

  • [2024-11-01 19:41:18]
  • 评测
  • 测评结果:100
  • 用时:1710ms
  • 内存:161380kb
  • [2024-11-01 19:41:17]
  • 提交

answer

//                              -    주의 만세!

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<tuple>

/*
0
15 6 6
1 7
2 7
13 1
14 2
12 14
3 14
12 8
3 11
8 4
5 4
10 7
6 10
3 9
15 14
2 9
3 2
2 5
8 2
2 15
1 14
4 3 5 2 15 14

*/

#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}

const int NV=5e5;
const ll mod=1e9+7;
int p2[NV+5],ip2[NV+5];
ll ksm(ll a,ll p){
    ll ans=1;
    while(p){
        if(p&1) ans=ans*a%mod;
        a=a*a%mod;
        p>>=1;
    }return ans;
}

int N;

namespace seg{
    struct SEGN{
        ll s,tml;
    } tr[NV*4+5];
    void domul(int x,ll z){
        tr[x].s=tr[x].s*z%mod;
        tr[x].tml=tr[x].tml*z%mod;
    }void dn(int x){
        if(tr[x].tml!=1){
            domul(x*2,tr[x].tml);
            domul(x*2+1,tr[x].tml);
            tr[x].tml=1;
        }
    }void up(int x){
        tr[x].s=(tr[x*2].s+tr[x*2+1].s)%mod;
    }void mul(int x,int l,int r,int ql,int qr,ll z){
        if(ql<=l&&r<=qr) return domul(x,z);
        int mid=l+r>>1;
        dn(x);
        if(ql<=mid) mul(x*2,l,mid,ql,qr,z);
        if(mid<qr) mul(x*2+1,mid+1,r,ql,qr,z);
        up(x);
    }void upd(int x,int l,int r,int p,ll z){
        if(l==r){
            tr[x].s=z;
            return;
        }
        int mid=l+r>>1;
        dn(x);
        if(p<=mid) upd(x*2,l,mid,p,z);
        else upd(x*2+1,mid+1,r,p,z);
        up(x);
    }ll que(int x,int l,int r,int ql,int qr){
        ll ans=0;
        int mid=l+r>>1;
        if(ql<=l&&r<=qr) return tr[x].s;
        dn(x);
        if(ql<=mid) ans=que(x*2,l,mid,ql,qr);
        if(mid<qr) ans=(ans+que(x*2+1,mid+1,r,ql,qr))%mod;
        return ans;
    }void dfs(int x,int l,int r){
        printf("%d[%d,%d]%lld\n",x,l,r,tr[x].s);
        if(l!=r){
            dn(x);
            int mid=l+r>>1;
            dfs(x*2,l,mid);
            dfs(x*2+1,mid+1,r);
        }
    }
}

namespace gph{
    std::vector<int> G[NV+5],vec[NV+5];
    int pr[20][NV+5],dfc,dfn[NV+5],dfr[NV+5],dep[NV+5],in[NV+5],out[NV+5];
    void dfs(int x,int p){
        pr[0][x]=p;
        for(int i=1;i<20;++i) pr[i][x]=pr[i-1][pr[i-1][x]];
        dfn[x]=++dfc;
        for(int t:G[x]) if(t!=p){
            dep[t]=dep[x]+1;
            dfs(t,x);
        }
        dfr[x]=dfc;
    }void dfssum(int x,int p){
        for(int t:G[x]) if(t!=p){
            dfssum(t,x);
            in[x]+=in[t];
            out[x]+=out[t];
        }
    }int kanc(int x,int k){
        for(int i=19;~i;--i) if(k>>i&1) x=pr[i][x];
        return x;
    }int lca(int x,int y){
        if(dep[x]<dep[y]) std::swap(x,y);
        for(int i=19;~i;--i) if(dep[pr[i][x]]>=dep[y]) x=pr[i][x];
        if(x==y) return x;
        for(int i=19;~i;--i) if(pr[i][x]!=pr[i][y]){
            x=pr[i][x];
            y=pr[i][y];
        }
        return pr[0][x];
    }
    std::vector<std::pair<int,int> > pat[NV+5];
    ll ans;
    bool key[NV+5];
    void dfs2(int x,int p){
        for(int t:G[x]) if(t!=p) dfs2(t,x);
        for(int t:vec[x]){
            seg::mul(1,1,N,dfn[t],dfr[t],2);
            ++gph::in[gph::kanc(t,
                    gph::dep[t]-gph::dep[x]-1)];
        }
        //seg::dfs(1,1,N);
        ll f0=1,f1=0,f2=0,f3=0;
        for(int t:G[x]) if(t!=p){
            ll g0=f0*p2[in[t]]%mod,g1=f1*p2[in[t]]%mod;
            ll g2=f2*p2[in[t]]%mod,g3=f3*p2[in[t]]%mod;
            ll f=seg::que(1,1,N,dfn[t],dfr[t]);
            //printf("%lld %lld %lld %lld %lld\n",g0,g1,g2,g3,f);
            g1=(g1+f0*f)%mod;
            g2=(g2+f1*f)%mod;
            g3=(g3+(f2+f3)*f)%mod;
            f0=g0;
            f1=g1;
            f2=g2;
            f3=g3;
        }
        //printf("%d: %lld %lld %lld %lld\n",x,f0,f1,f2,f3);
        //for(int i=1;i<=N;++i) printf("%d %d\n",in[i],out[i]);
        for(int t:G[x]) if(t!=p){
            seg::mul(1,1,N,dfn[t],dfr[t],ip2[in[t]]);
        }
        if(G[x].size()>1){
            std::vector<std::tuple<int,int,int,int> > arr;
            for(int t:G[x]) if(t!=p) arr.emplace_back(dfn[t],0,0,1);
            for(auto p:pat[x]){
                int u=p.fi,v=p.se;
                if(dfn[u]>dfn[v]) std::swap(u,v);
                arr.emplace_back(dfn[u],dfn[v],dfr[v],2);
                arr.emplace_back(dfr[u]+1,dfn[v],dfr[v],mod+1>>1);
            }
            std::sort(arr.begin(),arr.end());

            auto find=[&](int v){
                int l=0,r=G[x].size();
                while(l+1<r){
                    int m=l+r>>1;
                    if(dfn[G[x][m]]>v) r=m;
                    else l=m;
                }
                return dfn[G[x][r]];
            };

            int lst=dfn[x]+1;
            for(auto eve:arr){
                int X,ql,qr,C;
                std::tie(X,ql,qr,C)=eve;
                if(lst<X){
                    ll c=seg::que(1,1,N,lst,X-1);
                    c=c*seg::que(1,1,N,find(lst),dfr[x])%mod;
                    ans=(ans+(ll)c*p2[out[x]+in[x]])%mod;
                    lst=X;
                }
                if(C!=1){
                    seg::mul(1,1,N,ql,qr,C);
                }
            }
        }
        seg::mul(1,1,N,dfn[x]+1,dfr[x],p2[in[x]]);

        int f=key[x]?(mod*2-f0-f1)%mod:(f2+f3)%mod;
        seg::upd(1,1,N,dfn[x],f);
        ans=(ans+(f+mod-f2)*p2[out[x]])%mod;
    }
}

namespace xm{
    std::pair<int,int> E[NV+5];
    int c[NV+5];
    void _(){
        int M,K;

        p2[0]=ip2[0]=1;
        for(int i=1;i<NV+5;++i){
            p2[i]=p2[i-1]*2%mod;
            ip2[i]=ip2[i-1]*(mod+1>>1)%mod;
        }

        scanf("%*d%d%d%d",&N,&M,&K);
        for(int i=1,u,v;i<N;++i){
            scanf("%d%d",&u,&v);
            gph::G[u].push_back(v);
            gph::G[v].push_back(u);
        }
        gph::dfs(1,0);
        for(int i=1;i<=M;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            if(gph::dep[u]>gph::dep[v]) std::swap(u,v);
            E[i]={u,v};
            if(gph::dfn[u]<=gph::dfn[v]&&gph::dfn[v]<=gph::dfr[u]){
                int p=gph::kanc(v,gph::dep[v]-gph::dep[u]-1);
                ++gph::in[u];
                ++gph::out[u];
                ++c[gph::dfn[v]];
                --c[gph::dfr[v]+1];
                ++c[1];
                --c[gph::dfn[p]];
                ++c[gph::dfr[p]+1];
                gph::vec[u].push_back(v);
            }else{
                int p=gph::lca(u,v);
                if(gph::dfn[u]>gph::dfn[v]) std::swap(u,v);
                gph::pat[p].emplace_back(u,v);
                ++c[gph::dfn[u]];
                --c[gph::dfr[u]+1];
                ++c[gph::dfn[v]];
                --c[gph::dfr[v]+1];
            }
        }
        for(int i=1;i<=N;++i) c[i]+=c[i-1];
        gph::dfssum(1,0);
        //for(int i=1;i<=M;++i)
        //    if(gph::dfn[E[i].fi]<=gph::dfn[E[i].se]
        //            &&gph::dfn[E[i].se]<=gph::dfr[E[i].fi])
        //        ++gph::in[gph::kanc(E[i].se,
        //                gph::dep[E[i].se]-gph::dep[E[i].fi]-1)];
        for(int i=1;i<=N;++i) gph::out[i]=c[gph::dfn[i]]-gph::out[i];
        while(K--){
            int x;
            scanf("%d",&x);
            gph::key[x]=1;
        }
        //for(int i=1;i<=N;++i) printf("%d %d\n",gph::in[i],gph::out[i]);
        gph::dfs2(1,0);
        printf("%lld\n",(mod-gph::ans)%mod);
    }
}

int main(){
    xm::_();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 4
Accepted
time: 11ms
memory: 74540kb

input:

1
6 6 5
5 1
2 5
6 5
3 2
6 4
1 4
1 6
4 3
4 2
6 3
2 6
5 2 6 1 3

output:

22

result:

ok 1 number(s): "22"

Test #2:

score: 4
Accepted
time: 12ms
memory: 94264kb

input:

2
6 6 6
3 1
5 3
3 2
5 4
2 6
4 6
4 2
1 4
6 1
1 2
3 4
3 4 6 2 1 5

output:

46

result:

ok 1 number(s): "46"

Test #3:

score: 4
Accepted
time: 4ms
memory: 91920kb

input:

3
6 6 6
1 2
4 1
4 6
4 5
3 5
3 6
6 2
2 3
6 5
2 5
4 2
4 6 3 2 5 1

output:

46

result:

ok 1 number(s): "46"

Test #4:

score: 4
Accepted
time: 7ms
memory: 95668kb

input:

4
15 15 6
6 1
7 1
6 11
14 7
8 11
4 8
8 10
10 12
5 10
2 12
3 8
9 11
15 5
13 2
9 4
3 14
11 12
4 14
11 4
3 5
4 5
14 5
11 5
3 10
10 4
14 10
10 6
8 15
15 10
7 4 14 10 5 8

output:

1384

result:

ok 1 number(s): "1384"

Test #5:

score: 4
Accepted
time: 11ms
memory: 96840kb

input:

5
15 15 6
11 1
9 11
1 15
7 11
15 2
6 2
4 2
8 4
4 5
14 8
1 10
7 12
6 3
10 13
14 10
5 7
5 13
3 9
13 6
6 5
4 9
4 10
15 7
15 13
12 1
11 8
10 11
11 5
6 11
13 5 3 1 4 11

output:

744

result:

ok 1 number(s): "744"

Test #6:

score: 4
Accepted
time: 11ms
memory: 95512kb

input:

6
15 15 6
9 1
7 9
6 1
7 3
6 8
8 12
4 12
12 5
10 5
10 15
14 1
3 2
11 7
13 2
10 14
14 13
5 2
15 4
8 14
4 13
12 2
6 14
6 13
3 14
10 3
4 3
3 8
9 3
11 14
10 13 4 6 3 11

output:

1873

result:

ok 1 number(s): "1873"

Test #7:

score: 4
Accepted
time: 7ms
memory: 94092kb

input:

7
300 168 6
1 184
1 41
10 41
184 18
18 215
184 271
215 267
194 184
165 18
223 18
223 83
123 165
6 165
90 83
41 2
123 40
232 194
177 232
262 123
140 271
40 211
11 271
21 18
15 11
158 177
197 1
41 35
194 110
217 177
215 121
297 123
223 38
15 72
297 46
35 212
228 140
1 89
130 11
158 296
279 35
90 287
1...

output:

144500972

result:

ok 1 number(s): "144500972"

Test #8:

score: 4
Accepted
time: 8ms
memory: 96512kb

input:

8
300 161 6
1 67
67 273
273 213
67 232
213 32
213 111
215 232
137 32
11 232
16 137
20 137
285 273
1 284
110 11
46 285
156 67
46 263
213 250
146 213
263 78
39 110
270 67
175 110
175 170
216 1
111 281
175 209
118 110
112 39
115 285
250 205
237 111
124 284
46 197
187 281
156 60
236 111
1 103
211 156
26...

output:

484515026

result:

ok 1 number(s): "484515026"

Test #9:

score: 4
Accepted
time: 4ms
memory: 93888kb

input:

9
300 157 6
56 1
1 36
56 280
285 1
285 265
166 280
56 213
87 1
191 213
87 232
166 31
280 112
43 213
43 24
293 166
232 91
31 89
259 213
232 68
134 24
168 91
280 257
172 280
87 226
229 36
56 209
239 232
43 72
72 132
265 235
283 72
300 112
1 252
112 174
241 285
24 44
8 235
193 43
256 280
168 287
257 61...

output:

644455703

result:

ok 1 number(s): "644455703"

Test #10:

score: 4
Accepted
time: 12ms
memory: 96716kb

input:

10
300 299 120
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...

output:

926641430

result:

ok 1 number(s): "926641430"

Test #11:

score: 4
Accepted
time: 8ms
memory: 95060kb

input:

11
300 300 116
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...

output:

723203191

result:

ok 1 number(s): "723203191"

Test #12:

score: 4
Accepted
time: 8ms
memory: 95600kb

input:

12
300 300 200
198 1
1 169
139 169
139 289
13 139
198 265
1 45
61 13
139 58
265 130
289 210
109 265
169 114
250 139
250 140
89 130
77 169
250 74
136 13
224 45
45 164
61 217
58 148
249 77
248 289
118 210
89 262
136 146
65 45
13 242
293 61
295 224
230 265
115 230
136 98
78 130
164 184
240 109
89 212
2...

output:

316149672

result:

ok 1 number(s): "316149672"

Test #13:

score: 4
Accepted
time: 7ms
memory: 95880kb

input:

13
300 300 200
1 296
1 284
1 160
296 154
109 160
160 134
175 1
134 95
184 154
198 175
184 172
10 109
248 284
51 154
10 33
134 73
181 172
172 55
33 121
218 121
225 248
205 248
91 181
282 248
154 38
218 83
188 284
243 248
225 69
221 160
65 121
154 233
269 243
287 38
154 18
175 100
147 154
23 65
154 24...

output:

383331059

result:

ok 1 number(s): "383331059"

Test #14:

score: 4
Accepted
time: 8ms
memory: 95696kb

input:

14
300 295 200
1 155
1 160
24 155
1 59
160 290
5 155
24 258
59 33
1 264
152 264
160 190
159 190
5 139
1 69
24 68
33 161
81 290
84 33
5 227
45 84
191 1
288 45
6 69
155 114
24 4
159 181
151 227
1 8
151 165
4 221
101 190
74 290
23 221
128 221
246 24
123 290
23 80
25 152
73 80
73 26
133 159
288 7
44 26
...

output:

129954782

result:

ok 1 number(s): "129954782"

Test #15:

score: 4
Accepted
time: 4ms
memory: 94516kb

input:

15
300 299 200
1 272
1 205
238 272
170 205
272 32
32 192
243 170
59 192
170 97
205 169
86 59
252 32
4 32
40 252
50 86
289 169
59 122
289 128
3 1
32 258
289 229
289 145
3 48
97 84
41 40
35 258
238 127
48 179
129 127
9 145
50 295
243 27
177 127
292 295
170 95
295 43
218 170
55 169
278 35
81 50
155 128...

output:

90662829

result:

ok 1 number(s): "90662829"

Test #16:

score: 4
Accepted
time: 4ms
memory: 95560kb

input:

16
300 293 200
1 176
1 230
122 176
3 230
3 110
64 1
110 69
219 176
64 279
152 122
69 170
3 269
152 155
132 122
76 155
246 155
235 230
5 269
123 69
42 3
147 155
267 269
148 122
116 219
148 59
85 69
176 194
24 42
220 64
235 238
54 64
97 76
116 25
122 75
116 297
176 272
258 76
10 1
231 3
262 170
76 251...

output:

693422085

result:

ok 1 number(s): "693422085"

Test #17:

score: 4
Accepted
time: 384ms
memory: 152620kb

input:

17
200000 199883 97179
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
...

output:

306668123

result:

ok 1 number(s): "306668123"

Test #18:

score: 4
Accepted
time: 396ms
memory: 153208kb

input:

18
200000 199876 97287
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
...

output:

740342085

result:

ok 1 number(s): "740342085"

Test #19:

score: 4
Accepted
time: 518ms
memory: 122412kb

input:

19
200000 200000 133333
1 124760
44003 124760
37294 1
163294 1
124760 4221
1 118363
163294 130356
163294 26345
150233 124760
163294 71228
118363 185064
16012 4221
136324 4221
130356 159564
16012 82836
37294 117301
37294 113319
118985 118363
67201 130356
134497 44003
118985 184508
62789 4221
167242 1...

output:

394869877

result:

ok 1 number(s): "394869877"

Test #20:

score: 4
Accepted
time: 501ms
memory: 122512kb

input:

20
200000 200000 133333
140575 1
1 186893
181732 140575
79385 140575
181732 9627
186089 181732
186893 149538
186893 55018
140575 13029
186089 97797
164282 149538
18033 181732
55018 137342
1 136416
140575 148531
97797 1750
9627 9882
181032 55018
34757 55018
72967 181032
137342 70468
85420 136416
1803...

output:

533887309

result:

ok 1 number(s): "533887309"

Test #21:

score: 4
Accepted
time: 509ms
memory: 121588kb

input:

21
200000 200000 133333
1 101322
88622 101322
58269 101322
58269 180983
168242 101322
95381 1
193115 95381
190995 168242
101322 148011
62879 88622
101322 172145
120738 190995
15239 120738
80271 193115
168242 21478
125310 58269
193115 93056
172145 110789
13098 172145
148011 174687
173743 190995
85181...

output:

487737487

result:

ok 1 number(s): "487737487"

Test #22:

score: 4
Accepted
time: 558ms
memory: 123992kb

input:

22
200000 199999 133333
150539 1
150539 74762
1 34140
1 195593
164815 1
32085 195593
156066 32085
21074 34140
162900 34140
70220 195593
6115 32085
155396 70220
73894 150539
22486 195593
195593 19530
6115 146034
21074 40513
61074 146034
146034 198896
120389 195593
34219 61074
113107 1
195593 86095
64...

output:

367879330

result:

ok 1 number(s): "367879330"

Test #23:

score: 4
Accepted
time: 1656ms
memory: 161380kb

input:

23
500000 499999 333333
1 199660
284063 1
156514 199660
346277 1
199660 147381
284063 314108
147381 497971
248228 1
207371 284063
314108 165529
156514 452115
218249 248228
140112 1
395841 452115
337568 156514
314108 125202
310327 218249
446894 140112
490601 1
165529 179615
323005 207371
179615 57231...

output:

716372640

result:

ok 1 number(s): "716372640"

Test #24:

score: 4
Accepted
time: 1651ms
memory: 161020kb

input:

24
500000 499998 333333
65074 1
65074 304288
1 335471
59340 335471
304288 81779
81779 254965
59340 491338
108358 81779
59340 313254
59340 490077
150085 108358
304288 231400
108450 491338
108358 58590
215265 254965
14203 108450
222338 81779
313254 347805
136496 215265
173386 1
490077 183586
108358 20...

output:

47496457

result:

ok 1 number(s): "47496457"

Test #25:

score: 4
Accepted
time: 1710ms
memory: 158960kb

input:

25
500000 499997 333333
1 359765
359765 132729
101821 132729
1 357109
101821 393660
393660 141211
204917 1
393660 160129
204917 59682
165524 160129
359765 184850
39288 1
97240 165524
77900 101821
39288 343784
402651 1
181637 77900
351195 393660
77900 303404
357109 478493
403484 101821
357109 458913
...

output:

661767304

result:

ok 1 number(s): "661767304"

Extra Test:

score: 0
Extra Test Passed