QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#624824#6102. Query on a Treelmy11RE 0ms0kbC++231.4kb2024-10-09 16:40:522024-10-09 16:40:52

Judging History

This is the latest submission verdict.

  • [2024-10-09 16:40:52]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-10-09 16:40:52]
  • Submitted

answer

#include <bits/stdc++.h>
#define pii pair<int,int>
#define int long long
#define ll long long
using namespace std;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
vector<int> son[N];
int dep[N];
int f[N];

int dfs(int u, int fa) {
	f[u] = fa;
	dep[u] = dep[fa] + 1;
	for (auto v : son[u]) {
		if (v == fa)
			continue;
		dfs(v, u);
	}
}

struct node {
	int idx;
	int dep;
	bool operator < (const node &other) const {
		return dep < other.dep;
	}
};
int p[N];
int siz[N];

int  find(int x) {
	if (x == p[x])
		return x;
	return p[x] = find(p[x]);
}

void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		p[i] = i;
	for (int i = 1; i <= n - 1; i++) {
		int u, v;
		cin >> u >> v;
		son[u].push_back(v);
		son[v].push_back(u);
	}
	dfs(1, 0);
	int t;
	cin >> t;
	while (t--) {
		int k;
		cin >> k;
		vector<node>v;
		for (int i = 0; i < k; i++) {
			int x;
			cin >> x;
			v.push_back({x, dep[x]});
		}
		sort(v.begin(), v.end());
		map<int, int> mp;
		int ans = 0;
		for (int i = 0; i < k; i++) {
			int x = v[i].idx;
			if (mp[f[x]]) {

				p[x] = find(f[x]);
				siz[find(x)] += 1;
				ans += siz[find(x)];
			}
			mp[x] = 1;
		}
		for (int i = 0; i < k; i++) {
			int x = v[i].idx;
			p[x] = x;
			siz[x] = 0;
		}
		cout << ans << endl;
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//    int t;
//    cin>>t;
//    while(t--)
	solve();
}

详细

Test #1:

score: 0
Runtime Error

input:

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

output:


result: