이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 25;
int n, q;
vector <int> adj[MAXN];
ll dp[MAXN], dep[MAXN];
vector <int> cc[MAXN];
void dfs (int pos, int par) {
dp[pos] = 0; cc[pos].clear();
if (par == -1) {
dep[pos] = 0;
} else {
dep[pos] = 1 + dep[par];
}
if (adj[pos].size() == 1 && par != -1) {
cc[pos].push_back(pos);
return;
}
int cnt = 0;
for (auto j : adj[pos]) {
if (j != par) {
dfs(j, pos);
for (auto k : cc[j]) {
cnt++;
cc[pos].push_back(k);
dp[pos] += dep[k];
}
dp[pos] += dp[j];
}
}
if (cnt % 2 == 1) {
dp[pos] -= 2 * dep[pos] * (cnt / 2);
int u = -1;
for (auto j : cc[pos]) {
if (u == -1 || dep[j] < dep[u]) {
u = j;
}
}
dp[pos] -= dep[u];
cc[pos].clear(); cc[pos].push_back(u);
return;
}
if (par == -1) {
dp[pos] -= 2 * dep[pos] * (cnt / 2);
cc[pos].clear();
return;
}
dp[pos] -= 2 * dep[pos] * (cnt / 2 - 1);
int u = -1, v = -1;
for (auto j : cc[pos]) {
if (u == -1 || dep[j] < dep[u]) {
v = u; u = j;
} else if (v == -1 || dep[j] < dep[v]) {
v = j;
}
}
dp[pos] -= dep[u] + dep[v];
cc[pos].clear(); cc[pos] = {u, v};
return;
}
void solve () {
cin >> n >> q;
for (int i = 1; i < n; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
while (q--) {
int d; cin >> d;
vector <int> c;
for (int i = 1; i <= d; i++) {
int x; cin >> x;
c.push_back(x);
}
for (int i = 0; i < d; i++) {
adj[c[i]].push_back(n + i + 1);
adj[n + i + 1].push_back(c[i]);
}
int r = -1;
for (int i = 1; i <= n + d; i++) {
if (adj[i].size() >= 2) {
r = i;
break;
}
}
dfs(r, -1);
if (cc[r].empty()) {
cout << dp[r] << '\n';
} else {
cout << -1 << '\n';
}
for (int i = d - 1; i >= 0; i--) {
adj[c[i]].pop_back();
adj[n + i + 1].pop_back();
}
}
}
signed main () {
ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |