首页 > 代码库 > Codeforces Round #200 (Div. 1) D. Water Tree(dfs序加线段树)
Codeforces Round #200 (Div. 1) D. Water Tree(dfs序加线段树)
思路:
dfs序其实是很水的东西。 和树链剖分一样, 都是对树链的hash。
该题做法是:每次对子树全部赋值为1,对一个点赋值为0,查询子树最小值。
该题需要注意的是:当我们对一棵子树全都赋值为1的时候, 我们要查询一下赋值前子树最小值是不是0, 如果是的话, 要让该子树父节点变成0, 否则变0的信息会丢失。
细节参见代码:
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <stack> #include <ctime> #include <bitset> #include <cstdlib> #include <cmath> #include <set> #include <list> #include <deque> #include <map> #include <queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; typedef long double ld; const double eps = 1e-6; const double PI = acos(-1); const int mod = 1000000000 + 7; const int INF = 0x3f3f3f3f; // & 0x7FFFFFFF const int seed = 131; const ll INF64 = ll(1e18); const int maxn = 500000+10; int T,n,m,tot=0,in[maxn],out[maxn],minv[maxn<<2],setv[maxn<<2],pre[maxn]; vector<int> g[maxn]; void dfs(int u, int fa) { in[u] = ++tot; pre[u] = fa; int len = g[u].size(); for(int i = 0; i < len; i++) { int v = g[u][i]; if(v == fa) continue; dfs(v, u); } out[u] = tot; } void pushup(int o) { minv[o] = min(minv[o<<1], minv[o<<1|1]); } void pushdown(int l, int r, int o) { if(setv[o] != -1) { setv[o<<1] = setv[o<<1|1] = setv[o]; minv[o<<1] = minv[o<<1|1] = setv[o]; setv[o] = -1; } } void build(int l, int r, int o) { minv[o] = 0; setv[o] = -1; if(l == r) return ; int mid = (l + r) >> 1; build(l, mid, o<<1); build(mid+1, r, o<<1|1); } void update(int L, int R, int v, int l, int r, int o) { if(L <= l && r <= R) { minv[o] = v; setv[o] = v; return ; } int mid = (l + r) >> 1; pushdown(l, r, o); if(L <= mid) update(L, R, v, l, mid, o<<1); if(mid < R) update(L, R, v, mid+1, r, o<<1|1); pushup(o); } int query(int L, int R, int l, int r, int o) { if(L <= l && r <= R) { return minv[o]; } int mid = (l + r) >> 1; pushdown(l, r, o); int ans = INF; if(L <= mid) ans = min(ans, query(L, R, l, mid, o<<1)); if(mid < R) ans = min(ans, query(L, R, mid+1, r, o<<1|1)); pushup(o); return ans; } int main() { scanf("%d", &n); for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); build(1, n, 1); int q; scanf("%d", &q); while(q--) { int id, v; scanf("%d%d", &id, &v); if(id == 1) { int tmp = query(in[v], out[v], 1, n, 1); update(in[v], out[v], 1, 1, n, 1); if(!tmp && pre[v]) update(in[pre[v]], in[pre[v]], 0, 1, n, 1); } else if(id == 2) { update(in[v], in[v], 0, 1, n, 1); } else { printf("%d\n", query(in[v], out[v], 1, n, 1)); } } return 0; }
Codeforces Round #200 (Div. 1) D. Water Tree(dfs序加线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。