在敌占区的特务时常会碰头。敌占区有n个城市，为保证安全，中央经过侦查，只选择了n-1条较安全的道路作为特务们碰头可以走的道路。每次开会，中央会选择特务正在工作当中的最早开始工作的那一个所在城市作为开会地点。为保证特务安全，开会时，中央会派安全小队在每一条特务会经过的道路上进行保护。每次开会时，中央想知道需要保护的道路共有多少条。

有时中央会认为一个城市很重要，于是在这个城市安插一个特务（即使该城已有特务）；有时一个城市的敌人被干掉了，于是召回这个城市的特务（即使城中没有特务）。一开始中央还没有向敌占区派特务。

第一行两个整数n，m，表示城市数和中央的命令数。
接下来n-1行，每行两个整数x和y，表示x和y间有一条特务可以通过的道路。
接下来m行，每行开头一个字符：
若为 + ，接下来一个数w，表示中央在w安插了一名特务。
若为 - ，接下来一个数w，表示城市w的特务全被召回。
若为 ?，表示特务会议召开，问有多少道路需要被保护。
（+，-与数之间有空格）

对于每次特务会议召开，输出一行一个整数，表示需要被保护的道路数。

3 61 21 3+ 2+ 1+ 3?- 2?

21

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cctype>#include <algorithm>#include <set>using namespace std;int read() {	int x = 0, f = 1; char c = getchar();	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }	return x * f;}#define maxn 100010#define maxm 200010#define maxlog 20int n, q, m, head[maxn], nxt[maxm], to[maxm];void AddEdge(int a, int b) {	to[++m] = b; nxt[m] = head[a]; head[a] = m;	swap(a, b);	to[++m] = b; nxt[m] = head[a]; head[a] = m;	return ;}int Dfs[maxn], clo, Poi[maxn], Fa[maxlog][maxn], dep[maxn];void build(int u, int fa) {	Dfs[u] = ++clo; Poi[clo] = u;	Fa[0][u] = fa;	for(int i = 1; i < maxlog; i++) Fa[i][u] = Fa[i-1][Fa[i-1][u]];	for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa) {		dep[to[e]] = dep[u] + 1;		build(to[e], u);	}	return ;}int calc(int a, int b) {//	printf("in calc: %d %d\n", a, b);	int ans = dep[a] + dep[b];	if(dep[a] < dep[b]) swap(a, b);	for(int i = maxlog - 1; i >= 0; i--)		if(dep[a] - dep[b] >= (1 << i)) a = Fa[i][a];	for(int i = maxlog - 1; i >= 0; i--)		if(Fa[i][a] != Fa[i][b]) a = Fa[i][a], b = Fa[i][b];	int c = a == b ? a : Fa[0][b];	ans -= (dep[c] << 1);	return ans;}set <int> S;std :: set <int> :: iterator it, it2;int main() {	n = read(); q = read();	for(int i = 1; i < n; i++) {		int a = read(), b = read();		AddEdge(a, b);	}		build(1, 0);//	for(int i = 1; i <= n; i++) printf("(%d)%d ", i, Dfs[i]); putchar(‘\n‘);//	for(int i = 1; i <= n; i++) printf("%d ", Poi[i]); putchar(‘\n‘);	int ans = 0;	while(q--) {		char op[2]; scanf("%s", op);		if(op[0] == ‘+‘) {			int u = read();			if(S.count(Dfs[u])) continue;			if(S.size()) {				it = S.upper_bound(Dfs[u]);				int a = *it, b;				if(it == S.end()) a = *(S.begin());				if(it == S.begin()) {					it2 = S.end();					b = *(--it2);				}				else b = *(--it);				a = Poi[a]; b = Poi[b];				ans -= calc(a, b);				ans += calc(a, u); ans += calc(u, b);			}			S.insert(Dfs[u]);		}		if(op[0] == ‘-‘) {			int u = read();			if(!S.count(Dfs[u])) continue;			if(S.size()) {				it = S.upper_bound(Dfs[u]);				int a = *it, b;				if(it == S.end()) a = *(S.begin());				it = S.lower_bound(Dfs[u]);				if(it == S.begin()) {					it2 = S.end();					b = *(--it2);				}				else {					it2 = it;					b = *(--it2);				}				a = Poi[a]; b = Poi[b];				ans += calc(a, b);				ans -= calc(a, u); ans -= calc(u, b);			}			S.erase(Dfs[u]);		}		if(op[0] == ‘?‘) printf("%d\n", ans >> 1);	}		return 0;}/*13 10001 21 31 41 52 62 76 86 96 104 115 125 13?+ 13?+ 11?+ 9?*/