淀粉树求卡常

#include<bits/stdc++.h>
#define ll long long
using namespace std;
//multiset<int> ans;
struct mpq{
	priority_queue<int> q1,q2;
	void erase(int x){q2.push(x);}
	void insert(int x){q1.push(x);}
	int mx(){
		while(q1.size()&&q2.size()&&q1.top()==q2.top())q1.pop(),q2.pop();
		return q1.top();
	}
	int size(){return q1.size()-q2.size();}
}ans;
struct node{
	unordered_map<int,mpq> ump;
	mpq ans;
	int getans(){
		if(ans.size()<=1)return -1;
		int u=ans.mx(),u2;
		ans.erase(u);
		u2=ans.mx();
		ans.insert(u);
		return u+u2;
	}
	void insert(int v,int fr){
		bool ok=0,ok2=ump[fr].size();
		if(ump[fr].size())if(ump[fr].mx()<v)ans.erase(ump[fr].mx()),ok=1;
		ump[fr].insert(v);
		if(!ok2||ok)ans.insert(v);
	}
	void erase(int v,int fr){
		ans.erase(ump[fr].mx());
		ump[fr].erase(v);
		if(ump[fr].size())ans.insert(ump[fr].mx());
	}
	
}tree[100005];
unordered_map<int,int> dep[100005];
int siz[100005],cut[100005],fa[100005],cl[100005],n,a,b,c,q;
vector<pair<int,int> > edge[100005];
void dfs1(int u,int fa){
	siz[u]=1;
	for(auto i:edge[u]){
		if(i.first!=fa&&!cut[i.first])dfs1(i.first,u),siz[u]+=siz[i.first];
	}
}
int zx(int u,int fa,int rt){
	if((siz[rt]-siz[u])*2>siz[rt])return -1;
	bool ok=1;
	for(auto i:edge[u]){
		if(i.first!=fa&&!cut[i.first]){
			int re=zx(i.first,u,rt);
			if(~re)return re;
			if(siz[i.first]*2>siz[rt])ok=0;
		}
	}
	return (ok?u:-1);
}
void init(int u,int fa,int rt,int udep){
	dep[rt][u]=udep;
	for(auto i:edge[u]){
		if(i.first!=fa&&!cut[i.first]){
			init(i.first,u,rt,udep+i.second);
		}
	}
}
int dfz(int u){
	dfs1(u,0);
	u=zx(u,0,u);
	init(u,0,u,0);
	cut[u]=1;
	for(auto i:edge[u]){
		if(!cut[i.first])fa[dfz(i.first)]=u;
	}
	return u;
}
void to1(int u){
	for(int i=u,fr=u;i;fr=i,i=fa[i]){
		int tans=tree[i].getans();
		if(~tans)ans.erase(tans);
		tree[i].insert(dep[i][u],fr);
		tans=tree[i].getans();
		if(~tans)ans.insert(tans);
	}
}
void to0(int u){
	for(int i=u,fr=u;i;fr=i,i=fa[i]){
		int tans=tree[i].getans();
		if(~tans)ans.erase(tans);
		tree[i].erase(dep[i][u],fr);
		tans=tree[i].getans();
		if(~tans)ans.insert(tans);
	}
}
int cnt=0;
void change(int u){
	if(cl[u]==1)to0(u),cnt--;
	else to1(u),cnt++;
	cl[u]=!cl[u];
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>a>>b>>c;
		edge[a].emplace_back(b,c);
		edge[b].emplace_back(a,c);
	}
	dfz(1);
	for(int i=1;i<=n;i++)change(i);
	cin>>q;
	char c;
	int x;
	while(q--){
		cin>>c;
		if(c=='A'){
			if(!cnt)cout<<"They have disappeared.\n";
			else if(cnt==1)cout<<"0\n";
			else cout<<max(0,/**prev(ans.end())*/ans.mx())<<'\n';
		}else{
			cin>>x;
			change(x);
		}
	}
}