QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#479067 | #8716. 树 | Nienie0730 | RE | 0ms | 0kb | C++17 | 3.7kb | 2024-07-15 14:37:05 | 2024-07-15 14:37:06 |
answer
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const double eps = 1e-8;
int n, m, q;
int h[N], e[N << 1], ne[N << 1], idx;
int A[N], B[N];
int depth[N], fa[N][21];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs(int u) {
memset(depth, 0x3f, sizeof depth);
queue<int> q;
q.push(u);
depth[0] = 0;
depth[u] = 1;
while (q.size()) {
int t = q.front();
q.pop();
for (int i = h[t];i != -1;i = ne[i]) {
int j = e[i];
if (depth[j] > depth[t] + 1) {
depth[j] = depth[t] + 1;
q.push(j);
fa[j][0] = t;
for (int k = 1;k < 20;k++) {
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int k = 19;k >= 0;k--) {
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];
}
if (a == b) return a;
for (int k = 19;k >= 0;k--) {
if (fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}
int check(int a, int b) {
int p = lca(a, b);
if (p == b) return 0;
return 1;
}
int change(int i, bool ok) {
int t = check(B[i - 2], B[i - 1]);
if (t == 1) {
if (lca(B[i - 1], B[i]) == B[i - 1]) A[i - 1] = 0;
}
else {
int tt = lca(B[i - 2], B[i]);
if (tt == B[i - 1]) {
A[i - 1] = 0;
}
else {
tt = lca(B[i - 1], tt);
if (tt != B[i - 1]) A[i - 1] = 0;
}
}
if (ok) A[i] = 1;
}
void solve() {
cin >> n >> m >> q;
memset(h, -1, sizeof h);
for (int i = 1;i < n;i++) {
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
for (int i = 1;i <= m;i++) cin >> B[i];
bfs(1);
A[1] = A[2] = 1;
for (int i = 3;i <= m;i++)
change(i, false);
int sum = 0;
for (int i = 1;i <= m;i++) sum += A[i];
// for (int j = 1;j <= q;j++) {
// int a, b;
// cin >> a >> b;
// B[a] = b;
// int temp = 0;
// temp += A[a], A[a] = 1;
// if (a > 1) temp += A[a - 1], A[a - 1] = 1;
// if (a < m) temp += A[a + 1], A[a + 1] = 1;
// if (a > 2) {
// change(a, false);
// }
// if (a + 1 > 2 && a + 1 <= m) {
// change(a + 1, false);
// }
// if (a + 2 <= m) {
// change(a + 2, false);
// }
// int now = 0;
// now += A[a];
// if (a > 1) now += A[a - 1];
// if (a < m) now += A[a + 1];
// sum += now - temp;
// cout << sum << "\n";
// }
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
5 5 3 2 1 3 2 1 4 5 1 1 5 4 2 3 1 3 5 3 3 3