QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#770405#5020. 举办乘凉州喵,举办乘凉州谢谢喵PatrickStar0 0ms0kbC++144.7kb2024-11-21 21:43:132024-11-21 21:43:13

Judging History

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

  • [2024-11-21 21:43:13]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-21 21:43:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2e5;
int n, q;
vector<int> v[MAXN+5];
int fa[MAXN+5], dep[MAXN+5], siz[MAXN+5], heavy[MAXN+5], top[MAXN+5];
void d(int i) {
	siz[i] = 1;
	for (int p=0;p<v[i].size();p++) {
		if (v[i][p]!=fa[i]) {
			fa[v[i][p]] = i;
			dep[v[i][p]] = dep[i]+1;
			d(v[i][p]);
			siz[i]+=siz[v[i][p]];
			if (siz[v[i][p]]>siz[heavy[i]]) heavy[i] = v[i][p];
		}
	}
	return ;
}
int st[MAXN+5], en[MAXN+5], dfn[MAXN+5], tot;
void df(int i, int last) {
	st[i] = ++tot;
	dfn[tot] = i;
	top[i] = last;
	if (heavy[i]) df(heavy[i], last);
	for (int p=0;p<v[i].size();p++) {
		if (v[i][p]!=fa[i]&&v[i][p]!=heavy[i]) df(v[i][p], v[i][p]);
	}
	en[i] = tot;
	return ;
}
struct e{
	int id, k, x;
};
vector<e> d1[MAXN+5], d2[MAXN+5], d3[MAXN+5];
int ans[MAXN+5];
#define lowbit(x) ((x)&(-(x)))
int T[MAXN+5];
void insert(int i, int x) {
	i++;
	while (i<=n) {
		T[i]+=x;
		i+=lowbit(i);
	}
	return ;
}
int found(int i) {
	i++;
	int u = 0;
	while (i) {
		u+=T[i];
		i-=lowbit(i);
	}
	return u;
}
void dfs(int i, bool keep) {
	for (int p=0;p<v[i].size();p++) {
		if (v[i][p]!=fa[i]&&v[i][p]!=heavy[i]) dfs(v[i][p], 0);
	}
	if (heavy[i]) dfs(heavy[i], 1);
	for (int p=0;p<v[i].size();p++) {
		if (v[i][p]!=fa[i]&&v[i][p]!=heavy[i]) {
			for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
				insert(dep[dfn[k]], 1);
			}
		}
	}
	for (int p=0;p<d1[i].size();p++) {
		ans[d1[i][p].id]+=d1[i][p].x*found(dep[i]+d1[i][p].k);
	}
	insert(dep[i], 1);
	if (!keep) {
		for (int p=st[i];p<=en[i];p++) {
			insert(dep[dfn[p]], -1);
		}
	}
	return ;
}
void rec(int i) {
	for (int p=0;p<v[i].size();p++) {
		if (v[i][p]!=fa[i]&&v[i][p]!=heavy[i]) {
			for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
				insert(dep[dfn[k]]-dep[i], 1);
			}
		}
	}
	for (int p=0;p<d2[i].size();p++) {
		ans[d2[i][p].id]+=d2[i][p].x*found(d2[i][p].k);
	}
	for (int p=0;p<v[i].size();p++) {
		if (v[i][p]!=fa[i]) rec(v[i][p]);
	}
	for (int p=0;p<v[i].size();p++) {
		if (v[i][p]!=fa[i]&&v[i][p]!=heavy[i]) {
			for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
				insert(dep[dfn[k]]-dep[i], -1);
			}
		}
	}
	return ;
}
bool vis[MAXN+5];
int SIZ, rt, maxp[MAXN+5];
void getrt(int i, int last) {
	siz[i] = 1, maxp[i] = 0;
	st[i] = ++tot;
	dfn[tot] = i;
	for (int p=0;p<v[i].size();p++) {
		if (!vis[v[i][p]]&&v[i][p]!=last) {
			dep[v[i][p]] = dep[i]+1;
			getrt(v[i][p], i);
			siz[i]+=siz[v[i][p]];
			maxp[i] = max(maxp[i], siz[v[i][p]]);
		}
	}
	en[i] = tot;
	maxp[i] = max(maxp[i], SIZ-siz[i]);
	if (maxp[i]<maxp[rt]) rt = i;
	return ;
}
void divide(int i) {
	vis[i] = 1;
	insert(0, 1);
	for (int p=0;p<v[i].size();p++) {
		if (!vis[v[i][p]]) {
			for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
				insert(dep[dfn[k]]-dep[i], 1);
			}
		}
	}
	for (int p=0;p<v[i].size();p++) {
		if (!vis[v[i][p]]) {
			for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
				insert(dep[dfn[k]]-dep[i], -1);
			}
			for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
				int s = dfn[k];
				for (int j=0;j<d3[s].size();j++) {
					ans[d3[s][j].id]+=d3[s][j].x*found(d3[s][j].k-(dep[s]-dep[i]));
				}
			}
			for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
				insert(dep[dfn[k]]-dep[i], 1);
			}
		}
	}
	insert(0, -1);
	for (int p=0;p<d3[i].size();p++) {
		ans[d3[i][p].id]+=d3[i][p].x*found(d3[i][p].k);
	}
	for (int p=0;p<v[i].size();p++) {
		if (!vis[v[i][p]]) {
			for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
				insert(dep[dfn[k]]-dep[i], -1);
			}
		}
	}
	for (int p=0;p<v[i].size();p++) {
		if (!vis[v[i][p]]) {
			SIZ = siz[v[i][p]];
			rt = 0;
			getrt(v[i][p], 0);
			dep[rt] = 0;
			tot = 0;
			getrt(rt, 0);
			divide(rt);
		}
	}
	return ;
}
int main() {
	scanf("%d", &n);
	for (int p=1;p<n;p++) {
		int x, y;
		scanf("%d %d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	d(1);
	df(1, 1);
	scanf("%d", &q);
	for (int p=1;p<=q;p++) {
		int x, y, k;
		scanf("%d %d %d", &x, &y, &k);
		while (top[x]!=top[y]) {
			if (dep[top[x]]>dep[top[y]]) swap(x, y);
			d1[y].push_back({p, k, 1});
			d1[top[y]].push_back({p, k-1, -1});
			d2[fa[y]].push_back({p, k, 1});
			d2[fa[top[y]]].push_back({p, k, -1});
			ans[p]+=dep[y]-dep[top[y]]+1;
			y = fa[top[y]];
		}
		if (dep[x]>dep[y]) swap(x, y);
		ans[p]+=dep[y]-dep[x]+1;
		if (x!=y) {
			d1[y].push_back({p, k, 1});
			d2[fa[y]].push_back({p, k, 1});
			d2[x].push_back({p, k, -1});
		}
		d1[x].push_back({p, k, -1});
		d2[x].push_back({p, k, 1});
		d2[fa[x]].push_back({p, k, -1});
		d3[x].push_back({p, k, 1});
	}
	dfs(1, 0);
	rec(1);
	SIZ = maxp[0] = n;
	getrt(1, 0);
	dep[rt] = 0;
	tot = 0;
	getrt(rt, 0);
	divide(rt);
	for (int p=1;p<=q;p++) {
		printf("%d\n", ans[p]);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

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:


result:


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%