QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#624824 | #6102. Query on a Tree | lmy11 | RE | 0ms | 0kb | C++23 | 1.4kb | 2024-10-09 16:40:52 | 2024-10-09 16:40:52 |
Judging History
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