bzoj4551[TJOI2016HEOI2016]树

bzoj4551 [TJOI2016&HEOI2016]树

给定一棵有根树&＃xff0c;请支持一下两种操作&＃xff1a;

• 标记一个点
• 询问一个点最近一个打了标记的祖先

\(n,\ m\leq10^5\)

线段树

首先用 \(dfs\) 序转换为序列问题&＃xff0c;用线段树动态维护

打标记按照原树 \(dep\) 更新答案

实现时可以将点上的答案与 \(tag\) 合并

时间复杂度 \(O(n\log n)\)

代码

#include
using namespace std;#define mid ((s &＃43; t) >> 1)
#define lson k <<1, s, mid
#define rson k <<1 | 1, mid &＃43; 1, t
const int maxn &＃61; 1e5 &＃43; 10;
int val[maxn <<2];
int n, m, sz[maxn], dep[maxn], tid[maxn];vector e[maxn];int dfs(int u, int f) {static int now;tid[u] &＃61; &＃43;&＃43;now;int tmp &＃61; int(e[u].size());for (int i &＃61; 0; i }void pushtag(int k, int x) {if (dep[val[k]] }void pushdown(int k) {pushtag(k <<1, val[k]);pushtag(k <<1 | 1, val[k]);
}void build(int k, int s, int t) {if (s &＃61;&＃61; t) {val[k] &＃61; 1; return;}build(lson), build(rson);
}void upd(int k, int s, int t, int l, int r, int x) {if (dep[x] mid) upd(rson, l, r, x);
}int query(int pos) {int k &＃61; 1, s &＃61; 1, t &＃61; n;while (s }int main() {scanf("%d %d", &n, &m);for (int i &＃61; 1, u, v; i }