锐客网

  1. 首页 > it技术 > >

codeforces E. Tree Queries

codeforces

codeforces E. Tree Queries
文章图片

题目 题意： 给你一颗树，在给你 k k k个查询，问每一次查询是否有每一个点都在同一条链上，或者点距离链的距离为 1 1 1.
思路： 【codeforces E. Tree Queries】这题首先是要找到一条能够尽可能容纳多的点得链，所以我们直接找到最深得那个点得那条链就行了，然后我们把题目要求得每个点得父节点求出来（根节点除外），如果距离为 1 1 1得话，那么父节点一定在链上，但是最后得话我们如果判断都是在一条链上得，看他被访问得时间，一条链上得，那么进入得时间一定比最深得早，出去得时间一定比最深得晚。

#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef vector veci; typedef vector vecl; typedef pair pii; template inline void read(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return ; while (c != '-' && (c < '0' || c > '9')) c = getchar(); sgn = (c == '-') ? -1:1; ret = (c == '-') ? 0:(c - '0'); while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return ; } inline void out(int x) { if (x > 9) out(x / 10); putchar(x % 10 + '0'); } const int maxn = 2e5 + 10; int n, m, cnt = 0; veci edge[maxn]; int deep[maxn], pr[maxn], tin[maxn], tout[maxn]; void dfs(int u, int pre, int dep) { deep[u] = dep; pr[u] = pre; tin[u] = cnt++; for (int i = 0; i < edge[u].size(); i++) { int v = edge[u][i]; if (v != pre) dfs(v, u, dep + 1); } tout[u] = cnt++; } int main() { read(n), read(m); for (int i = 0; i < n - 1; i++) { int u, v; read(u), read(v); edge[u].push_back(v); edge[v].push_back(u); } dfs(1, -1, 0); while (m--) { int k, x, maxdep = 0, maxu = 1; read(k); veci vi; for (int i = 0; i < k ; i++) { read(x); vi.push_back(x); if (maxdep < deep[x]) maxdep = deep[x], maxu = x; } bool flag = false; for (int i = 0; i < vi.size(); i++) { if (vi[i] != 1 && vi[i] != maxu) vi[i] = pr[vi[i]]; if (tin[maxu] < tin[vi[i]] || tout[maxu] > tout[vi[i]]) { flag = true; break; } } if (!flag) printf("YES\n"); else printf("NO\n"); } return 0; }

    推荐阅读


    上一篇：BFS|Solve The Maze（codeforces）

    下一篇：扩展欧几里得算法的证明