QTREE4

QTREE4.cpp

#include <cstdio>
#include <queue>
using std::priority_queue;
const int N = 100000 + 9,INF = 0x3f3f3f3f;
int son[N],nxt[N * 2],lnk[N * 2],len[N * 2],dis[N],ec;
struct info
{
	int u,dis;
	info(const int _u = 0,const int _dis = 0):
		u(_u),dis(_dis){}
};
inline bool operator<(const info &lhs,const info &rhs){return lhs.dis < rhs.dis;}
priority_queue<info>gans,sq[N * 3];
bool iscenter[N];
int n,cnt,col[N],sqa[N * 3],D[20][N],Times[N];
inline bool check(const info &a)
{
	return sqa[a.u] != a.dis;
}
struct Center_info
{
	int fa,fa_son,ans;
	priority_queue<info>q;
	void calc(int idx)
	{
		while (!q.empty() && check(q.top())) q.pop();
		if (q.empty()) return(void)(ans = -INF);
		info tmp = q.top(),t; q.pop();
		while (!q.empty() && (check(t = q.top()) || t.u == tmp.u)) q.pop();
		if (q.empty()) {ans = (col[idx] ? -INF : tmp.dis); q.push(tmp); return;}
		ans = tmp.dis + q.top().dis;
		q.push(tmp);
	}
	void update(const int idx)
	{
		calc(idx);
		gans.push(info(idx,ans));
	}
	//Center_info(){q.push(info(0,-INF));q.push(info(0,-INF));}
}c[N];
int FC(int s)
{
	static int q[N],fa[N],f[N],g[N];
	g[0] = INF;
	int h = 1,t = 1,res = 0;
	f[s] = g[s] = fa[s] = 0;
	//fa[s] = 0;
	for (q[t] = s; h <= t; ++h)
		for (int v,i = son[q[h]]; i; i = nxt[i]) {
			if (iscenter[v = lnk[i]] || v == fa[q[h]]) continue;
			q[++t] = v;
			fa[v] = q[h];
			f[v] = g[v] = 0;
		}
	for (int i = t; i; --i) {
		f[fa[q[i]]] += (++f[q[i]]);
		g[fa[q[i]]] = std::max(g[fa[q[i]]],f[q[i]]);
		g[q[i]] = std::max(g[q[i]],t - f[q[i]]);
		if (g[q[i]] < g[res]) res = q[i];
	}
	iscenter[res] = true;
	return res;
}
void update(int s)
{
	static int q[N],fa[N],pre[N];
	int h = 1,t = 1;
	fa[s] = dis[s] = 0; D[++Times[s]][s] = 0;
	sq[2 * n + s].push(info(s,0));
	sqa[2 * n + s] = std::max(sqa[2 * n + s],0);
	for (q[t] = s; h <= t; ++h)
		for (int i = son[q[h]],v; i; i = nxt[i]) {
			if (iscenter[v = lnk[i]] || fa[q[h]] == v) continue;
			q[++t] = v;
			if (q[h] == s) pre[v] = i;
			else pre[v] = pre[q[h]];
			fa[v] = q[h];
			D[++Times[v]][v] = dis[v] = dis[q[h]] + len[i];
			sq[pre[v]].push(info(v,dis[v]));
			sqa[pre[v]] = std::max(sqa[pre[v]],dis[v]);
		}
	for (int v,i = son[s]; i; i = nxt[i])
		if (!iscenter[v = lnk[i]] && fa[s] != v)
			c[s].q.push(info(i,sqa[i]));
	c[s].q.push(info(2 * n + s,0));
	c[s].update(s);
}
void init()
{
	static int q[N];
	int h = 1,t = 1;
	for (q[t] = FC(1); h <= t; ++h) {
		update(q[h]);
		for (int i = son[q[h]]; i; i = nxt[i])
			if (!iscenter[lnk[i]]) {
				q[++t] = FC(lnk[i]);
				c[q[t]].fa = q[h];
				c[q[t]].fa_son = i;
			}
	}
}	
inline void addedge(const int x,const int y,const int z)
{
	nxt[++ec] = son[x];
	son[x] = ec;
	lnk[ec] = y;
	len[ec] = z;
}
void modify(int x)
{
	int s = x;
	if (col[x] ^= 1) sq[2 * n + x].pop();
	else sq[2 * n + x].push(info(x,0)),c[x].q.push(info(2 * n + x,0));
	sqa[2 * n + x] = sq[2 * n + x].top().dis;
	cnt -= (col[x] ? 1 : -1);
	c[s].update(s);
	for (int t = Times[x] - 1; c[x].fa; x = c[x].fa,--t) {
		int y = c[x].fa_son,dis = D[t][s];
		//printf("Test: %d %d %d\n",c[x].fa,s,dis);
		if (!col[s]) sq[y].push(info(s,dis));
		while (!sq[y].empty() && col[sq[y].top().u]) sq[y].pop();
		if (sqa[y] != sq[y].top().dis) {
			sqa[y] = sq[y].top().dis;
			if (sqa[y] != -INF) c[c[x].fa].q.push(info(y,sqa[y]));
		}
		c[c[x].fa].update(c[x].fa);
	}
}
void read(int &x)
{
	char c = getchar(),p = '.';
	for (; c < '0' || c > '9'; c = getchar()) p = c;
	x = 0;
	for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
	if (p == '-') x = -x;
}
int main()
{
	//scanf("%d",&n);
	read(n);
	cnt = n;
	for (int i = 1; i <= n * 3; ++i) sq[i].push(info(0,-INF)),sqa[i] = -INF;
	for (int i = 1,x,y,z; i < n; ++i) {
		//scanf("%d%d%d",&x,&y,&z);
		read(x); read(y); read(z);
		addedge(x,y,z);
		addedge(y,x,z);
	}
	init();
	int m;
	//scanf("%d",&m);
	read(m);
	for (int x; m--; ) {
		char ch = getchar();
		while (ch != 'A' && ch != 'C') ch = getchar();
		if (ch == 'A') {
			if (!cnt) {puts("They have disappeared.");continue;}
			while (!gans.empty() && (c[gans.top().u].ans != gans.top().dis)) gans.pop();
			printf("%d\n",gans.top().dis);
		}else {
			//scanf("%d",&x);
			read(x);
			modify(x);
		}
	}
}