自闭了

有没有同错第4个点的童鞋分享一下修改经验

代码如下

#include<bits/stdc++.h>
using namespace std;

template<typename T>
inline void Read(T &n){
	char ch; bool flag=false;
	while(!isdigit(ch=getchar())) if(ch=='-')flag=true;
	for(n=ch^48; isdigit(ch=getchar()); n=(n<<1)+(n<<3)+(ch^48));
	if(flag) n=-n;
}
#define no !

const int MAXN = 100005;
const int MAXK = 17;

struct _{
	int nxt, to;
	_(int nxt=0, int to=0):nxt(nxt),to(to){}
}edge[MAXN<<1];
int fst[MAXN], tot;

inline void Add_Edge(int f, int t){
	edge[++tot] = _(fst[f], t); fst[f] = tot;
	edge[++tot] = _(fst[t], f); fst[t] = tot;
}

struct Set{
	priority_queue<int>ins,del;
	
	inline void push(int val){ins.push(val);}
	inline void erase(int val){if(ins.empty()==false and ins.top()==val) ins.pop(); else del.push(val);}
	
	inline int top(){
		while(ins.empty()==false and del.empty()==false and ins.top()==del.top())ins.pop(),del.pop();
		return ins.empty() ? -INT_MAX : ins.top();
	}
	
	inline int ans(){
		int temp=top(); if(temp==-INT_MAX) return -1;
		erase(temp); int tmp=top(); if(tmp==-INT_MAX){push(temp); return 0;}
		push(temp); return temp+tmp;
	}
}q1[MAXN], Ans, q2[MAXN];

bool vis[MAXN], Vis[MAXN];

int sz[MAXN];
int Total_Size, Center, Min_Weight;
void Find_Center(int x){
	vis[x] = true;
	
	sz[x] = 1;
	int res=0;
	for(register int u=fst[x]; u; u=edge[u].nxt){
		int v=edge[u].to;
		if(vis[v] or Vis[v]) continue;
		Find_Center(v);
		sz[x] += sz[v];
		res = max(res,sz[v]);
	}
	res = max(Total_Size-sz[x],res);
	
	if(res<Min_Weight)
		Center = x,
		Min_Weight = res;
	
	vis[x] = false;
}

int dis[MAXN][17], now_dep, now_fa, dep[MAXN];
void Get_Dis(int x){
	vis[x] = true;
	
	q2[Center].push(dis[x][now_dep]);
//	printf("q2[%d].push(%d)\n",Center,dis[x][now_dep]);
	sz[x] = 1;
	for(register int u=fst[x]; u; u=edge[u].nxt){
		int v=edge[u].to;
		if(vis[v] or Vis[v]) continue;
		dis[v][now_dep] = dis[x][now_dep]+1;
		Get_Dis(v);
		sz[x] += sz[v];
	}
	
	vis[x] = false;
}

void Calc_Size(int x){
	vis[x] = true;
	sz[x] = 1;
	for(register int u=fst[x]; u; u=edge[u].nxt){
		int v=edge[u].to;
		if(vis[v] or Vis[v]) continue;
		Calc_Size(v);
		sz[x] += sz[v];
	}
	vis[x] = false;
}

int fa[MAXN];
int Divide(int x, int depth){
	Min_Weight = Total_Size+1; Find_Center(x); now_dep = depth;
	if(depth) dis[x][now_dep] = 1, Get_Dis(x);
	x = Center; dep[x] = depth; Vis[x] = true;
//	for(register int i=1; i<=depth; i++) putchar('-');printf("%d\n",x);
	
	q1[x].push(0); Calc_Size(x);
//	printf("q1[%d].push(0)\n",x);
	for(register int u=fst[x]; u; u=edge[u].nxt){
		int v=edge[u].to;
		if(Vis[v]) continue;
		Total_Size = sz[v];
		int nxt=Divide(v,depth+1);
		fa[nxt] = x;
		q1[x].push(q2[nxt].top());
//		printf("q1[%d].push(%d)\n",x,q2[nxt].top());
	}
	Ans.push(q1[x].ans());
//	printf("Ans.push(%d)\n",q1[x].ans());
	
	return x;
}

bool Open[MAXN];
inline void Update(){
	int x; Read(x);
	for(register int i=x, depth=dep[x]; i; i=fa[i], depth--){
		int temp=q2[i].top();
		if(Open[x]) q2[i].push(dis[x][depth]);
//			printf("q2[%d].push(%d)\n",i,dis[x][depth]);
		else q2[i].erase(dis[x][depth]);
//			printf("q2[%d].erase(%d)\n",i,dis[x][depth]);
		
		if(fa[i] and temp!=q2[i].top()){
			int tmp = q1[fa[i]].ans();
			q1[fa[i]].erase(temp);
			q1[fa[i]].push(q2[i].top());
//			printf("q1[%d].erase(%d)\n",fa[i],temp);
//			printf("q1[%d].push(%d)\n",fa[i],q2[i].top());
			if(q1[fa[i]].ans()!=tmp)
				Ans.erase(tmp),
				Ans.push(q1[fa[i]].ans());
//				printf("Ans.erase(%d)\n",tmp),
//				printf("Ans.push(%d)\n",q1[fa[i]].ans());
		}
	}
	Open[x] ^= 1;
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	int n; Read(n);
	for(register int i=1; i<n; i++){
		int f, t;
		Read(f); Read(t);
		Add_Edge(f,t);
	}
	
	Total_Size = n; Divide(1,0);
	
//	int maxdep=0;
//	for(register int i=1; i<=n; i++) maxdep=max(maxdep,dep[i]);
//	for(register int i=1; i<=n; i++,puts(""))
//		for(register int j=0; j<=maxdep; j++)
//			printf("%d ",dis[i][j]);
	
	int Q; Read(Q);
	while(Q--){
//		puts("");
		char opt; do opt=getchar(); while((opt^'G')and(opt^'C'));
		if(opt=='G') printf("%d\n",Ans.top());
		if(opt=='C') Update();
	}
	
	return 0;
}
/*
8
3 2
2 8
3 6
3 1
3 5
2 7
1 4
5
G
C 4
G
C 4
G
*/