首页 > 代码库 > bzoj3637 Query on a tree VI
bzoj3637 Query on a tree VI
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3637
【题解】
LCT维护连通性问题。
发现如果直接按题目说的复杂度就是错的了(因为依赖于度数)
所以我们分黑白建树,黑的里存白->黑和黑->黑两种边,白的类似。
那么每次只会改变两棵树内的各一个。
因为LCT维护连通性所以需要记录除了主链外的其他size。
在access的时候即可记录。
这个link和cut很迷啊暂时没看懂啊(逃)参考别人代码
留坑
# include <stdio.h> # include <string.h> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 2e5 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, head[M], nxt[M], to[M], tot=0; bool color[M]; inline void add(int u, int v) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; } inline void adde(int u, int v) {add(u, v), add(v, u);} struct LCT { int co, ch[M][2], fa[M], sz[M], SZ[M]; bool rev[M]; inline void change(int x, int d) { sz[x] += d; SZ[x] += d; } inline void set(int n, int _co) { co = _co; memset(ch, 0, sizeof ch); memset(fa, 0, sizeof fa); memset(rev, 0, sizeof rev); memset(sz, 0, sizeof sz); memset(SZ, 0, sizeof SZ); if(!co) for (int i=1; i<=n; ++i) change(i, 1); } # define ls ch[x][0] # define rs ch[x][1] inline void up(int x) { if(!x) return; sz[x] = sz[ls] + sz[rs] + SZ[x]; } # undef ls # undef rs inline bool isrt(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; } inline void rotate(int x) { int y = fa[x], z = fa[y], ls = ch[y][1] == x, rs = ls^1; if(!isrt(y)) ch[z][ch[z][1] == y] = x; fa[ch[x][rs]] = y, fa[y] = x, fa[x] = z; ch[y][ls] = ch[x][rs]; ch[x][rs] = y; up(y); up(x); } inline void splay(int x) { while(!isrt(x)) { int y = fa[x], z = fa[y]; if(!isrt(y)) { if((ch[y][0] == x)^(ch[z][0] == y)) rotate(x); else rotate(y); } rotate(x); } } inline int access(int x) { int t = 0; for (; x; t=x, x=fa[x]) { splay(x); if(ch[x][1]) SZ[x] += sz[ch[x][1]]; if(t) SZ[x] -= sz[t]; ch[x][1] = t; up(x); } return t; } inline void link(int x, int y) { if(!y) return; access(y); splay(y); splay(x); fa[x] = y; ch[y][1] = x; up(y); } inline void cut(int x, int y) { if(!y) return; access(x); splay(x); fa[ch[x][0]] = 0, ch[x][0] = 0; up(x); } inline int find(int x) { access(x); splay(x); while(ch[x][0]) x = ch[x][0]; return x; } inline void getans(int x) { int t = find(x); splay(t); if(color[t] == co) printf("%d\n", sz[t]); else printf("%d\n", sz[ch[t][1]]); } }T[2]; // T[0]: black, T[1]: white // color0: black, color1: white int fa[M]; inline void dfs(int x, int father) { fa[x] = father; for (int i=head[x]; i; i=nxt[i]) { if(to[i] == father) continue; T[0].link(to[i], x); dfs(to[i], x); } } int main() { scanf("%d", &n); for (int i=1, u, v; i<n; ++i) { scanf("%d%d", &u, &v); adde(u, v); } T[0].set(n, 0); T[1].set(n, 1); dfs(1, 0); // for (int i=1; i<=n; ++i) T[0].getans(i); puts("\n==============="); int q; scanf("%d", &q); int opt, x; while(q--) { scanf("%d%d", &opt, &x); if(opt == 0) T[color[x]].getans(x); else { T[color[x]].cut(x, fa[x]); T[color[x]].change(x, -1); color[x] ^= 1; T[color[x]].change(x, 1); T[color[x]].link(x, fa[x]); } } return 0; }
bzoj3637 Query on a tree VI
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。