洛谷:P3950 部落冲突

原题地址:https://www.luogu.org/problemnew/show/P3950

题目简述

给定一棵树，每次给定一个操作，有如下两种：

1. 将某条边染黑
   2.询问给定的u,v两点间是否有边被染黑

---

思路

询问两点间是否有边被染黑只需要在求LCA时判一下就行。所以直接上树链剖分即可。
本题不需要使用线段树，使用树状数组查询路径上是否有任意一段区间和不为0即可。

---

代码

#include <bits/stdc++.h>
#define lowbit(x) x&-x
using namespace std;
typedef pair<int, int> P;
const int maxn = 1000000;
P war[maxn];
int fa[maxn], dep[maxn], val[maxn], sz[maxn], top[maxn], son[maxn];
int tre[maxn];
int tot;
int cntw;
int n, m;
inline int read()
{int ch, x = 0, f = 1;ch = getchar();while((ch < '0' || ch > '9') && ch != '-') ch = getchar();ch == '-' ? f = -1, ch = getchar() : 0;while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return f * x;
}
struct Edge {int to, len, nxt;Edge() {}Edge(int _to, int _len, int _nxt):to(_to), len(_len), nxt(_nxt) {}
}E[maxn];
int h[maxn], cnte;
int L[maxn], R[maxn];
void update(int x, int add) {for(int i = x;i <= maxn; i += lowbit(i)) tre[i] += add;
}
int query(int x) {int ans = 0; for(int i = x; i; i -= lowbit(i)) ans += tre[i]; return ans;
}
inline void add_edge(int u, int v, int w) {E[++cnte] = Edge(v, w, h[u]), h[u] = cnte;E[++cnte] = Edge(u, w, h[v]), h[v] = cnte;
}
void dfs1(int x) {sz[x] = 1; dep[x] = dep[fa[x]] + 1;for(int i = h[x]; i; i = E[i].nxt) {int to = E[i].to;if(to == fa[x]) continue;fa[to] = x;val[x] = E[i].len;dfs1(to);sz[x] += sz[to];if(sz[to] > sz[son[x]]) son[x] = to;}}
void dfs2(int x) {L[x] = ++tot;if(x == son[fa[x]]) top[x] = top[fa[x]];else top[x] = x;if(son[x]) dfs2(son[x]);for(int i = h[x]; i; i = E[i].nxt) {int to = E[i].to;if(to == fa[x] || to == son[x]) continue;dfs2(to);}R[x] = tot;
}void cut(int x, int y) {if(L[x] < L[y]) swap(x, y);update(L[x], 1);
}
void connect(int x, int y) {if(L[x] < L[y]) swap(x, y);update(L[x], -1);
}
int qsum(int x, int y) {//其实可以查到有1就退出，不用查完和int ans = 0;while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]])swap(x, y);ans += (query(L[x]) - query(L[top[x]] - 1));x = fa[top[x]];}if(dep[x] < dep[y])swap(x, y);if (x!=y)ans += (query(L[x]) - query(L[y]));return ans;
}
signed main() {scanf("%d%d", &n, &m);for(int i = 1; i < n; i++) add_edge(read(), read(), 0);dfs1(1);dfs2(1);for(int i = 1;i <= m; i++) {char s[50];cin >> s;if(s[0] == 'C') {int u = read(), v = read();cut(u, v);war[++cntw] = P(u, v);} else if(s[0] == 'U') {int w = read();connect(war[w].first, war[w].second);}else {if(qsum(read(), read()) != 0) puts("No");else puts("Yes");}}return 0;
}