【题目大意】
维护一个$n$个点的图，$m$个操作，支持两个操作：
1. 连接$(u, v)$这条边；
2. 询问$u$所在的联通块中，能选出的最大合法的点数。
一个方案是合法的，当且仅当对于所有被选择的点，他们都没有直接通过一条边相连。
$n leq 2*10^5, mleq 8*10^5$
【题解】
考虑用LCT来维护这个图。
对于实边的Splay，维护$h_it_j$，其中$i, j in {0, 1}$，表示前面选择$i$，后面选择$j$。（选0表示不选，选1表示选）
这个是可以合并信息的。
考虑虚边，对于每个虚边连到的实边的点，维护$l_i$，其中$i in {0,1}$，分别表示$l_i$必须为0，以及$l_i$可以为0的值。
那么$l_i$可以通过连的虚边的值转移来。
那么连到的实边的点的val就可以用$l_i$表示。
在access的时候和link的时候（link可以用两个makeroot来做）支持实边虚边转换即可。
# include <stdio.h> # include <assert.h> # include <iostream> # include <string.h> # include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; inline int getint() { int x = 0; char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = (x<<3) + (x<<1) + ch - '0', ch = getchar(); return x; } const int N = 2e5 + 10, M = 5e5 + 10, inf = 1e9; int n, m; struct node { int h0t0, h0t1, h1t0, h1t1; node () {} node (int h0t0, int h0t1, int h1t0, int h1t1) : h0t0(h0t0), h0t1(h0t1), h1t0(h1t0), h1t1(h1t1) {} inline friend node operator + (node a, node b) { // a tail with b head node p; p.h0t0 = max(a.h0t1 + b.h0t0, a.h0t0 + max(b.h1t0, b.h0t0)); p.h0t1 = max(a.h0t1 + b.h0t1, a.h0t0 + max(b.h1t1, b.h0t1)); p.h1t0 = max(a.h1t1 + b.h0t0, a.h1t0 + max(b.h1t0, b.h0t0)); p.h1t1 = max(a.h1t1 + b.h0t1, a.h1t0 + max(b.h1t1, b.h0t1)); return p; } inline int gans() { return max(max(h0t0, h0t1), max(h1t0, h1t1)); } inline void prt() { printf("{%d %d %d %d}", h0t0, h0t1 == -inf ? -1 : h0t1, h1t0 == -inf ? -1 : h1t0, h1t1); } }; struct LCT { node p[N], val[N]; int l0[N], l1[N]; int ch[N][2], fa[N]; bool rev[N]; # define ls ch[x][0] # define rs ch[x][1] inline void up(int x) { if(!x) return ; // ... p[x] = val[x]; if(ls) p[x] = p[ls] + p[x]; if(rs) p[x] = p[x] + p[rs]; } inline void pushrev(int x) { if(!x) return ; swap(ch[x][0], ch[x][1]); // ... swap(p[x].h1t0, p[x].h0t1); rev[x] ^= 1; } inline void down(int x) { if(!x) return ; if(rev[x]) { pushrev(ls); pushrev(rs); rev[x] ^= 1; } } # 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); } int st[N]; inline void splay(int x) { int stn = 0, tx = x; while(!isrt(tx)) st[++stn] = tx, tx = fa[tx]; st[++stn] = tx; for (int i=stn; i; --i) down(st[i]); while(!isrt(x)) { int y = fa[x], z = fa[y]; if(!isrt(y)) { if((ch[z][0] == y) ^ (ch[y][0] == x)) rotate(x); else rotate(y); } rotate(x); } } inline void del(int y, int x) { int p0 = max(p[x].h0t0, p[x].h0t1), p1 = max(p[x].h1t0, p[x].h1t1); l0[y] += p0; l1[y] += max(p0, p1); } inline void ins(int y, int x) { int p0 = max(p[x].h0t0, p[x].h0t1), p1 = max(p[x].h1t0, p[x].h1t1); l0[y] -= p0; l1[y] -= max(p0, p1); } inline int access(int x) { int t = 0; for (; x; t = x, x = fa[x]) { splay(x); // ... if(ch[x][1]) del(x, ch[x][1]); if(t) ins(x, t); val[x].h0t0 = l1[x]; val[x].h1t1 = l0[x] + 1; ch[x][1] = t; up(x); } return t; } inline void makeroot(int x) { access(x); splay(x); pushrev(x); } inline void link(int x, int y) { makeroot(x); makeroot(y); fa[x] = y; // ... int p0 = max(p[x].h0t0, p[x].h0t1), p1 = max(p[x].h1t0, p[x].h1t1); l0[y] += p0; l1[y] += max(p0, p1); val[y].h0t0 = l1[y]; val[y].h1t1 = l0[y] + 1; up(y); } inline void debug() { for (int x=1; x<=n; ++x) { printf("x = %d,fa = %d,ls = %d,rs = %d, p = ", x, fa[x], ch[x][0], ch[x][1]); p[x].prt(); printf(", val = "); val[x].prt(); printf(", l0 = %d,l1 = %d ", l0[x], l1[x]); } } }T; int main() { freopen("game.in", "r", stdin); freopen("game.out", "w", stdout); n = getint(); for (int x=1; x<=n; ++x) { T.val[x] = T.p[x] = node(0, -inf, -inf, 1); T.ch[x][0] = T.ch[x][1] = T.fa[x] = 0; T.rev[x] = 0; T.l0[x] = T.l1[x] = 0; } register int Q = getint(), op, u, v; while(Q--) { // T.debug(); op = getint(), u = getint(); if(op == 0) { T.makeroot(u); printf("%d ", T.p[u].gans()); // cout << ... << endl; } else { v = getint(); T.link(u, v); } } return 0; }