QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#306898#5020. 举办乘凉州喵,举办乘凉州谢谢喵YeahPotato0 11ms36932kbC++145.2kb2024-01-17 15:31:572024-01-17 15:31:58

Judging History

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

  • [2024-01-17 15:31:58]
  • 评测
  • 测评结果:0
  • 用时:11ms
  • 内存:36932kb
  • [2024-01-17 15:31:57]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = N << 1;
int n, q, u, v, k, lca, edgenum, Head[N], Next[M], vet[M], ans[N];
int fa[N], dep[N], siz[N], son[N], top[N];
int mx, tree[N], P, id[N], val[N], tag[N], tot, cg, Max[N], _mx, buc[N], exc[N], vis[N], cur, stk[N], le[N], ri[N];
struct qry { int a, b, c; } ; basic_string <qry> hpath[N], subtree[N], single[N];
int read() {
	int s = 0; char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s;
}
void write(int x) {
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
void add(int u, int v) {
	Next[++edgenum] = Head[u];
	Head[u] = edgenum;
	vet[edgenum] = v;
}
void dfs1(int u, int f) {
	fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (v ^ f) {
			dfs1(v, u), siz[u] += siz[v];
			if (siz[v] > siz[son[u]]) son[u] = v;
		}
	}
}
void dfs2(int u, int t) {
	top[u] = t;
	if (son[u]) dfs2(son[u], t);
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (v != fa[u] && v != son[u])
			dfs2(v, v);
	}
}
int getlca(int u, int v) {
	while (top[u] ^ top[v]) {
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	} return dep[u] < dep[v] ? u : v;
}
void addq(int u, int k, int i, int c) {
	ans[i] += c * dep[u];
	while (u) {
		if (son[u] && k) subtree[son[u]] += (qry) {k - 1, i, c};
		hpath[u] += (qry) {k, i, c};
		if (fa[u=top[u]] && k) subtree[u] += (qry) {k - 1, i, - c};
		u = fa[u];
	}
}
void update(int s) {
	for (; s<=n; s+=s&-s) tree[s] ++;
}
int getsum(int s) {
	int res = 0;
	for (; s; s-=s&-s) res += tree[s];
	return res;
}
void clear(int s) {
	for (; s<=n && tree[s]; s+=s&-s) tree[s] = 0;
}
void dfs3(int u, int d) {
	mx = max(mx, d), update(d);
	for (int e=Head[u]; e; e=Next[e])
		if (vet[e] ^ fa[u])
			dfs3(vet[e], d + 1);
}
void solvehpath(int u) {
	int _ = u; mx = 0;
	for (; u; u=son[u]) {
		for (int e=Head[u]; e; e=Next[e]) {
			int v=vet[e];
			if (v == fa[u] || v == son[u]) continue;
			dfs3(v, 1);
		}
		for (qry t : hpath[u])
			ans[t.b] += t. c * getsum(t. a);
	}
	for (int i=1; i<=mx; i++) clear(i);
	for (u=_; u; u=son[u])
		for (int e=Head[u]; e; e=Next[e]) {
			int v=vet[e];
			if (v != fa[u] && v != son[u])
				solvehpath(v);
		}
}
void dfs4(int u) {
	dep[u] = son[u] = 0;
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (v ^ fa[u]) {
			dfs4(v), dep[u] = max(dep[u], dep[v] + 1);
			if (dep[v] > dep[son[u]]) son[u] = v;
		}
	}
}
void solvesubtree(int u) {
	if (! id[u]) id[u] = P + 1, P += dep[u] + 1;
	if (son[u]) id[son[u]] = id[u] + 1, solvesubtree(son[u]);
	tag[u] = tag[son[u]];
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (v == fa[u] || v == son[u]) continue;
		solvesubtree(v), tag[u] += tag[v] + val[id[v]+dep[v]];
		for (int i=0; i<=dep[v]; i++)
			val[id[u]+i+1] += val[id[v]+i] - val[id[v]+dep[v]];
	} val[id[u]] = 1 - tag[u];
	for (qry t : subtree[u])
		ans[t.b] += t. c * (val[id[u]+min(t.a,dep[u])] + tag[u]);
}
#define find(u,s) (tot = s, cg = 0, getroot(u, 0), cg)
void getroot(int u, int fa) {
	siz[u] = 1;
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (v != fa && ! vis[v]) {
			getroot(v, u), siz[u] += siz[v];
			Max[u] = max(Max[u], siz[v]);
		}
	} Max[u] = max(Max[u], tot - siz[u]);
	if (Max[u] < Max[cg]) cg = u;
}
void dfs5(int u, int fa, int d) {
	mx = max(mx, d), stk[++cur] = d, buc[d] ++;
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (v != fa && ! vis[v])
			dfs5(v, u, d + 1);
	}
}
void dfs6(int u, int fa, int d) {
	for (qry t : single[u])
		if (t. a >= d)
			ans[t.b] += t. c * (buc[min(t.a-d,mx)] - exc[min(t.a-d,_mx)]);
	siz[u] = 1;
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (v != fa && ! vis[v])
			dfs6(v, u, d + 1), siz[u] += siz[v];
	}
}
void solvesingle(int u) {
	vis[u] = 1, stk[cur=1] = 0, buc[mx=0] = 1;
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (vis[v]) continue;
		le[v] = cur + 1, dfs5(v, u, 1), ri[v] = cur;
	}
	for (int i=1; i<=mx; i++) buc[i] += buc[i-1];
	for (qry t : single[u]) ans[t.b] += t. c * buc[min(t.a,mx)];
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (vis[v]) continue;
		_mx = 0;
		for (int i=le[v]; i<=ri[v]; i++) _mx = max(_mx, stk[i]), exc[stk[i]] ++;
		for (int i=1; i<=_mx; i++) exc[i] += exc[i-1];
		dfs6(v, u, 1);
		for (int i=1; i<=_mx; i++) exc[i] = 0;
	}
	for (int i=0; i<=mx; i++) buc[i] = 0;
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (! vis[v]) solvesingle(find(v, siz[v]));
	}
}
int main() {
	n = read();
	for (int i=1; i<n; i++)
		u = read(), v = read(), add(u, v), add(v, u);
	dfs1(1, 0), dfs2(1, 1);
	q = read();
	for (int i=1; i<=q; i++) {
		u = read(), v = read(), k = read(), lca = getlca(u, v);
		if (v == lca) swap(u, v);
		if (u ^ v)
			if (u ^ lca) addq(u, k, i, 1), addq(v, k, i, 1), addq(lca, k, i, - 2);
			else addq(v, k, i, 1), addq(u, k, i, - 1);
		single[lca] += (qry) {k, i, 1};
	}
	solvehpath(1);
	dfs4(1), solvesubtree(1);
	Max[0] = 1e9, solvesingle(find(1, n));
	for (int i=1; i<=q; i++)
		write(ans[i]), putchar('\n');
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 11ms
memory: 36932kb

input:

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

output:

3512
2199
6586
209
254
4586
4406
2164
6399
2188
308
393
5830
314
5439
5598
6232
1546
6149
12
1920
5324
6392
5370
19
82
6539
5392
209
5430
472
3998
809
1944
214
3902
1231
272
84
5174
3730
70
81
5225
6389
674
5903
6187
113
496
75
164
210
2282
6294
4929
100
3426
234
66
5126
535
6064
392
5371
2481
15
55...

result:

wrong answer 1st numbers differ - expected: '3226', found: '3512'

Subtask #2:

score: 0
Runtime Error

Test #9:

score: 0
Runtime Error

input:

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

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Test #25:

score: 0
Runtime Error

input:

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

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%