QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397816 | #8546. Min or Max 2 | comeintocalm# | RE | 0ms | 0kb | C++20 | 2.3kb | 2024-04-24 17:16:12 | 2024-04-24 17:16:13 |
answer
#include <bits/stdc++.h>
const int N = 1e5 + 5;
int n, q;
struct SegTree {
int a[N];
void insert(int p, int k) {
for (; p <= n; p += (p & -p)) {
a[p] += k;
}
}
int ask(int p, int ret = 0) {
for (; p; p -= (p & -p)) {
ret += a[p];
}
return ret;
}
} bit;
std::vector<int> ver[N];
int dfn[N], tot;
int dep[N], siz[N], hson[N], fa[N];
int f[N][17];
void dfs(const int u) {
dfn[u] = ++tot;
for (int i = 1; i < 17; ++i) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
siz[u] = 1;
for (auto &&v: ver[u]) {
if (v == fa[u]) {
continue;
}
dep[v] = dep[u] + 1;
fa[v] = u;
f[v][0] = u;
dfs(v);
siz[u] += siz[v];
}
}
int getLca(int u, int v) {
if (dep[u] > dep[v]) {
std::swap(u, v);
}
for (int i = 16; i >= 0; --i) {
if (dep[f[v][i]] >= dep[u]) {
v = f[v][i];
}
}
if (u == v) {
return u;
}
for (int i = 16; i >= 0; --i) {
if (f[u][i] == f[v][i]) {
u = f[u][i], v = f[v][i];
}
}
return f[u][0];
}
int getPos(int u, int v) {
for (int i = 16; i >= 0; --i) {
if (dep[f[u][i]] > dep[v]) {
u = f[u][i];
}
}
return u;
}
int query(int p) {
return bit.ask(dfn[p] + siz[p] - 1) - bit.ask(dfn[p] - 1);
}
int main() {
std::cin.tie(0)->sync_with_stdio(false);
std::cin >> n >> q;
for (int i = 1; i < n; ++i) {
int u, v;
std::cin >> u >> v;
ver[u].emplace_back(v);
ver[v].emplace_back(u);
}
dfs(1);
while (q--) {
int k;
std::cin >> k;
std::vector<int> a(k);
for (auto &ai: a) {
std::cin >> ai;
}
if (k == 1) {
std::cout << "Yes\n";
continue;
}
std::vector<std::pair<int,int>> roll_back(k - 1);
bool flag = false;
for (size_t i = 0; i + 1 < k; ++i) {
int lca = getLca(a[i], a[i + 1]);
int pos = getPos(a[i], lca);
bit.insert(pos, dep[a[i]] - dep[lca]);
roll_back[i] = {pos, dep[a[i]] - dep[lca]};
int qwq = query(pos);
if (qwq == siz[pos]) {
flag = true;
break;
}
}
if (flag) {
std::cout << "No\n";
} else {
std::cout << "Yes\n";
}
for (auto &&[p, k] : roll_back) {
bit.insert(p, -k);
}
}
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
4 2 1 2 2 1 5 2 4 1 5 3 2 4 1 5 3 5 1 2 3 4 5 5 4 3 2 1 8 5 8 3 4 2 7 1 6 4 6 3 8 5 1 2 7