SPOJ QTREE6 lct

題目鏈接

島娘出的題。還是比較easy的

#include <iostream>
#include <fstream>
#include <string>
#include <time.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
template <class T>
inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ?

-1 : 1; ret = (c == '-') ?

0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if (x>9) pt(x / 10); putchar(x % 10 + '0'); } typedef long long ll; typedef pair<int, int> pii; const int N = 100005; const int inf = 10000000; struct Node *null; struct Node { Node *fa, *ch[2]; int id; int s[2];//s[0] this虛邊所連的全部子樹的連續白色點數總和（不是鏈） int col; int ls[2], rs[2], siz; //ls[0]是對于這條鏈 最上端向下的連續白色點數 int Ls[2], Rs[2]; //Ls[0]是對于這棵子樹 與最上端點相連的連續白色點數 bool rev; inline void clear(int _col, int _id) { fa = ch[0] = ch[1] = null; siz = 1; rev = 0; id = _id; col = _col; for (int i = 0; i < 2; i++) { ls[i] = rs[i] = s[i] = 0; } } inline void push_up() { if (this == null)return; siz = ch[0]->siz + ch[1]->siz + 1; for (int i = 0; i < 2; i++) { ls[i] = ch[0]->ls[i], rs[i] = ch[1]->rs[i]; Ls[i] = ch[0]->Ls[i], Rs[i] = ch[1]->Rs[i]; if (ch[0]->ls[i] == ch[0]->siz && i == col) { ls[i] = ch[0]->siz + 1 + ch[1]->ls[i]; Ls[i]++; Ls[i] += s[i]; Ls[i] += ch[1]->Ls[i]; } if (ch[1]->rs[i] == ch[1]->siz && i == col) { rs[i] = ch[1]->siz + 1 + ch[0]->rs[i]; Rs[i]++; Rs[i] += s[i]; Rs[i] += ch[0]->Rs[i]; } } } inline void push_down() { if (rev) { ch[0]->flip(); ch[1]->flip(); rev = 0; } } inline void setc(Node *p, int d) { ch[d] = p; p->fa = this; } inline bool d() { return fa->ch[1] == this; } inline bool isroot() { return fa == null || fa->ch[0] != this && fa->ch[1] != this; } inline void flip() { if (this == null)return; swap(ch[0], ch[1]); rev ^= 1; } inline void go() {//從鏈頭開始更新到this if (!isroot())fa->go(); push_down(); } inline void rot() { Node *f = fa, *ff = fa->fa; int c = d(), cc = fa->d(); f->setc(ch[!c], c); this->setc(f, !c); if (ff->ch[cc] == f)ff->setc(this, cc); else this->fa = ff; f->push_up(); } inline Node*splay() { go(); while (!isroot()) { if (!fa->isroot()) d() == fa->d() ? fa->rot() : rot(); rot(); } push_up(); return this; } inline Node* access() {//access后this就是到根的一條splay。而且this已經是這個splay的根了 for (Node *p = this, *q = null; p != null; q = p, p = p->fa) { p->splay(); if (p->ch[1] != null) for (int i = 0;i < 2;i++) p->s[i] += p->ch[1]->Ls[i]; if (q != null) for (int i = 0; i < 2; i++) p->s[i] -= q->Ls[i]; p->setc(q, 1); p->push_up(); } return splay(); } inline Node* find_root() { Node *x; for (x = access(); x->push_down(), x->ch[0] != null; x = x->ch[0]); return x; } void make_root() { access()->flip(); } void cut() {//把這個點的子樹脫離出去 access(); ch[0]->fa = null; ch[0] = null; push_up(); } void cut(Node *x) { if (this == x || find_root() != x->find_root())return; else { x->make_root(); cut(); } } void link(Node *x) { if (find_root() == x->find_root())return; else { make_root(); fa = x; } } }; Node pool[N], *tail; Node *node[N]; int n, q; struct Edge { int to, nex; }edge[N << 1]; int head[N], edgenum; void add(int u, int v) { Edge E = { v, head[u] }; edge[edgenum] = E; head[u] = edgenum++; } void dfs(int u, int fa) { for (int i = head[u]; ~i; i = edge[i].nex) { int v = edge[i].to; if (v == fa)continue; node[v]->fa = node[u]; dfs(v, u); for (int j = 0; j < 2; j++) node[u]->s[j] += node[v]->Ls[j]; } node[u]->push_up(); } int main() { while (cin >> n) { memset(head, -1, sizeof head); edgenum = 0; for (int i = 1, u, v; i < n; i++) { rd(u); rd(v); add(u, v);add(v, u); } tail = pool; null = tail++; null->clear(-1, 0); null->siz = 0; for (int i = 1; i <= n; i++) { node[i] = tail++; node[i]->clear(1, i); } dfs(1, 1); rd(q); int u, v; while (q--) { rd(u); rd(v); if (!u) { node[v]->access(); pt(max(node[v]->Rs[0], node[v]->Rs[1])); puts(""); } else { node[v]->access(); node[v]->col ^= 1; node[v]->push_up(); } } } return 0; }