QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#80709#5403. 树数术zhouhuanyi0 2191ms153148kbC++142.7kb2023-02-24 21:49:192023-02-24 21:49:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-24 21:49:20]
  • 评测
  • 测评结果:0
  • 用时:2191ms
  • 内存:153148kb
  • [2023-02-24 21:49:19]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#define N 700000
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int n,m,q,depth[N+1],a[N+1],fa[N+1],lg[N+1],hs[N+1],dfn[N+1],top[N+1],leng,sz[N+1],tong[N+1],length;
bool used[N+1];
long long ans;
vector<int>E[N+1];
void add(int x,int y)
{
    E[x].push_back(y),E[y].push_back(x);
    return;
}
void dfs(int x)
{
    used[x]=sz[x]=1;
    for (int i=0;i<E[x].size();++i)
	if (!used[E[x][i]])
	{
	    fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,dfs(E[x][i]),sz[x]+=sz[E[x][i]];
	    if (sz[E[x][i]]>sz[hs[x]]) hs[x]=E[x][i];
	}
    return;
}
void dfs2(int x)
{
    dfn[x]=++leng;
    if (hs[x]) top[hs[x]]=top[x],dfs2(hs[x]);
    for (int i=0;i<E[x].size();++i)
	if (fa[E[x][i]]==x&&E[x][i]!=hs[x])
	    top[E[x][i]]=E[x][i],dfs2(E[x][i]);
    return;
}
int lca(int x,int y)
{
    while (top[x]!=top[y])
    {
	if (depth[top[x]]<depth[top[y]]) swap(x,y);
	x=fa[top[x]];
    }
    if (depth[x]<depth[y]) swap(x,y);
    return y;
}
bool LENG(int x,int y)
{
    return dfn[x]<=dfn[y]&&dfn[y]<=dfn[x]+sz[x]-1;
}
struct seg
{
    struct node
    {
	int l,r,data,res;
    };
    node tree[(N<<2)+1];
    void build(int k,int l,int r)
    {
	tree[k].l=l,tree[k].r=r,tree[k].data=a[l],tree[k].res=1;
	for (int i=l+1;i<=r;++i)
	{
	    tree[k].data=lca(tree[k].data,a[i]);
	    if (tree[k].data==a[i]) tree[k].res++;
	}
	if (l==r) return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid),build(k<<1|1,mid+1,r);
	return;
    }
    int query(int k,int d)
    {
	if (tree[k].l==tree[k].r) return LENG(d,tree[k].data);
	if (LENG(tree[k<<1].data,d)) return query(k<<1,d)+tree[k].res-tree[k<<1].res;
	else if (LENG(d,tree[k<<1].data)) return query(k<<1|1,d);
	else return query(k<<1|1,lca(d,tree[k<<1].data));
    }
    void solve(int k,int l,int r)
    {
	if (tree[k].l==l&&tree[k].r==r)
	{
	    tong[++length]=k;
	    return;
	}
	int mid=(tree[k].l+tree[k].r)>>1;
	if (r<=mid) solve(k<<1,l,r);
	else if (l>=mid+1) solve(k<<1|1,l,r);
	else solve(k<<1,l,mid),solve(k<<1|1,mid+1,r);
	return;
    }
};
seg T;
int main()
{
    int k,x,y,l,r,d;
    n=read(),m=read(),q=read();
    for (int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
    for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
    depth[1]=top[1]=1,dfs(1),dfs2(1);
    for (int i=1;i<=m;++i) a[i]=read();
    T.build(1,1,m);
    while (q--)
    {
	k=read(),length=0;
	while (k--) l=read(),r=read(),T.solve(1,l,r);
	d=T.tree[tong[1]].data,ans=T.tree[tong[1]].res;
	for (int i=2;i<=length;++i) ans+=T.query(tong[i],d),d=lca(d,T.tree[tong[i]].data);
	printf("%lld\n",ans);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1798ms
memory: 153148kb

input:

699990 699995 233333
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...

output:

122060
139525
87469
42807
311786
194311
177806
454200
417122
299507
366096
227761
186415
163955
292515
216120
401703
16625
192712
27344
52126
54929
142186
275124
339854
117007
51157
229183
187646
350022
398520
83936
100513
338065
356683
60212
366252
142638
16914
222321
471114
184168
170757
238373
14...

result:

wrong answer 1st lines differ - expected: '121987', found: '122060'

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 2191ms
memory: 125172kb

input:

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

output:

211596
160848
176726
128252
32659
70708
74879
9096
68278
91328
154262
24278
31878
173467
75271
139717
91661
87526
194302
16874
81534
172916
29151
20486
151882
5256
9550
58885
38079
94152
14354
74848
48869
23980
41391
60974
13802
125820
425
26642
130621
174232
73242
55289
2360
78870
23392
4867
36002
...

result:

wrong answer 1st lines differ - expected: '211594', found: '211596'

Subtask #3:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 177ms
memory: 47928kb

input:

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

output:

9731
11330
8401
5134
22203
23232
12681
27289
23732
20941
18149
16379
8991
14029
11665
14680
20270
18954
21668
7929
21383
23574
14818
5715
15705
10009
7908
13252
13881
10442
16137
16791
11004
11915
15767
20420
11159
12185
14328
18250
19087
5240
4112
16504
7415
5002
16844
8742
19374
22600
12022
9162
9...

result:

wrong answer 1st lines differ - expected: '9733', found: '9731'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%