题目链接

岛娘出的题。还是比較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;

}