LCT，但常数太大TLE80

#include<bits/stdc++.h>
#define fa(p) tr[p].fa
#define lc(p) tr[p].ch[0]
#define rc(p) tr[p].ch[1]
#define nr(p) (lc(fa(p))==p||rc(fa(p))==p)
using namespace std;
typedef long long ll;
const int mxn=1e6+10,inf=1e9;
int n,q,ans,c[mxn];
inline int max(int a,int b){
	return a>b?a:b;
} 
int p[mxn<<1],nxt[mxn<<1],h[mxn],ev[mxn<<1],tot;
void add(int x,int y,int v){
	tot++;
	p[tot]=y;
	nxt[tot]=h[x];
	h[x]=tot;
	ev[tot]=v;
}
struct M{
	int y,v;
};
vector<M> e[mxn];
struct N{
	int ch[2],fa,v,w,s,ml,mr,mx;
	multiset<int> pa,cha;
}tr[mxn];
int get1(multiset<int> s){
	if(!s.size())return -inf;
	return *s.rbegin();
}
int get2(multiset<int> s){
	if(s.size()<2)return -inf;
	return *(++s.rbegin());
}
void pushup(int p){
	tr[p].s=tr[lc(p)].s+tr[rc(p)].s+tr[p].v;
	int ch=max(tr[p].w,get1(tr[p].cha));
	int l=max(ch,tr[lc(p)].mr+tr[p].v),r=max(ch,tr[rc(p)].ml);
	tr[p].ml=max(tr[lc(p)].ml,tr[lc(p)].s+tr[p].v+r);
	tr[p].mr=max(tr[rc(p)].mr,tr[rc(p)].s+l);
	tr[p].mx=max({tr[lc(p)].mr+tr[p].v+r,tr[rc(p)].ml+l,tr[lc(p)].mx,tr[rc(p)].mx,get1(tr[p].pa),get1(tr[p].cha)+get2(tr[p].cha)});
	if(tr[p].w==0)tr[p].mx=max(tr[p].mx,max(get1(tr[p].cha),0));
}
void dfs(int x){
//	cout<<x<<" ";
	for(int i=h[x];i;i=nxt[i])if(p[i]!=fa(x)){
		int y=p[i];
		fa(y)=x;
		tr[y].v=ev[i];
		dfs(y);
		tr[x].cha.insert(tr[y].ml);
		tr[x].pa.insert(tr[y].mx);
	}
	pushup(x);
}
void rotate(int x){
	int y=fa(x),z=fa(y),k=rc(y)==x;
	if(nr(y))tr[z].ch[rc(z)==y]=x;fa(x)=z;
	tr[y].ch[k]=tr[x].ch[k^1];fa(tr[x].ch[k^1])=y;
	tr[x].ch[k^1]=y;fa(y)=x;
	pushup(y);pushup(x);
}
void splay(int x){
	while(nr(x)){
		int y=fa(x),z=fa(y);
		if(nr(y))((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y);
		rotate(x); 
	}
}
void access(int x){
	for(int y=0;x;){
		splay(x);
		if(rc(x))tr[x].cha.insert(tr[rc(x)].ml),tr[x].pa.insert(tr[rc(x)].mx);
		if(y)tr[x].cha.erase(tr[x].cha.find(tr[y].ml)),tr[x].pa.erase(tr[x].pa.find(tr[y].mx));
		rc(x)=y;
		pushup(x);
		y=x;x=fa(x);
	}
}
void change(int x){
	access(x);
	splay(x);
	c[x]^=1;
	tr[x].w=(c[x]?(-inf):0);
	pushup(x);
	ans=tr[x].mx;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=0;i<=n;i++){
		tr[i].ml=tr[i].mr=tr[i].mx=-inf;
	}
	for(int i=1,x,y,v;i<n;i++){
		cin>>x>>y>>v;
		add(x,y,v);add(y,x,v);
	}
	dfs(1);
	ans=tr[1].mx;
	cin>>q;
	while(q--){
		char c;
		cin>>c;
		if(c=='C'){
			int x;
			cin>>x;
			change(x);
		}
		else{
			if(ans<0)cout<<"They have disappeared.\n";
			else cout<<ans<<'\n';
		}
	}
	return 0;
}

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
bool be;
constexpr int N=1e6+10;
typedef long long ll;
constexpr ll inf=2e18;
struct _z{
	int c[2];
	ll mxa,tg,pdtg;
}z[40*N];int cnt;
void upd(int &u,int cl,int cr,int ql,int qr,ll v){
	if(!u){u=++cnt;z[u].mxa=z[u].tg=z[u].pdtg=-inf;}if(cl>=ql && cr<=qr){z[u].tg=max(z[u].tg,v);return;}
	int mid=(cl+cr)>>1;if(ql<=mid) upd(z[u].c[0],cl,mid,ql,qr,v);if(qr>mid) upd(z[u].c[1],mid+1,cr,ql,qr,v);
}
void add(int u,ll v){z[u].mxa=max(z[u].mxa,z[u].tg+v),z[u].pdtg=max(z[u].pdtg,v);}
void pd(int u){if(z[u].pdtg!=-inf){if(z[u].c[0]) add(z[u].c[0],z[u].pdtg);if(z[u].c[1]) add(z[u].c[1],z[u].pdtg);z[u].pdtg=-inf;}}
int merge(int u,int v,int cl,int cr,ll mxu,ll mxv,ll bs){
	if(!u && !v) return 0;if(!u){add(v,mxu);return v;}if(!v){add(u,mxv);return u;}
	mxu=max(mxu,bs+z[u].tg),mxv=max(mxv,bs+z[v].tg);add(u,mxv);add(v,mxu);pd(u),pd(v);
	z[u].mxa=max(z[u].mxa,z[v].mxa),z[u].tg=max(z[u].tg,z[v].tg);int mid=(cl+cr)>>1;
	z[u].c[0]=merge(z[u].c[0],z[v].c[0],cl,mid,mxu,mxv,bs);z[u].c[1]=merge(z[u].c[1],z[v].c[1],mid+1,cr,mxu,mxv,bs);return u;
}
int rt[N],m,cur[N],ct,n;ll dep[N],ans[N];
vector<pair<int,int> > es[N];
void dfs(int u,int fa){
	for(auto v:es[u]) if(v.first!=fa)
		dep[v.first]=dep[u]+v.second,dfs(v.first,u);
}
void dfs2(int u,int fa){
	for(auto v:es[u]) if(v.first!=fa)
		dfs2(v.first,u),rt[u]=merge(rt[u],rt[v.first],1,m,-inf,-inf,-2ll*dep[u]);
}
char s[5];bool nok[N];
vector<pair<int,int> > ss[N];
void solve(int u,int cl,int cr,ll curm){
	if(u) pd(u);int mid=(cl+cr)>>1;curm=max(curm,z[u].mxa);
	if(cl==cr){ans[cl]=curm;return;}solve(z[u].c[0],cl,mid,curm);solve(z[u].c[1],mid+1,cr,curm);
}
bool ed;
int main(){
  //printf("%0.2lf M\n",(&ed-&be)/1024.0/1024.0);
	scanf("%d",&n);ct=n;
	for(int i=1;i<=n;++i)
		cur[i]=1;
	for(int i=1,u,v,w;i<n;++i)
		scanf("%d%d%d",&u,&v,&w),es[u].push_back(make_pair(v,w)),es[v].push_back(make_pair(u,w));
	dfs(1,0);
	int q;scanf("%d",&q);
	for(int i=1,t;i<=q;++i){
		scanf("%s",s);
		if(s[0]=='A'){++m;nok[m]=(ct==0);}
		else{
			scanf("%d",&t);
			if(cur[t]){
				--ct;if(cur[t]<=m) ss[t].push_back(make_pair(cur[t],m));
				cur[t]=0;
			}else{
				++ct;cur[t]=m+1;
			}
		}
	}
	if(!m) return 0;
	for(int i=1;i<=n;++i){
		if(cur[i] && cur[i]<=m) ss[i].push_back(make_pair(cur[i],m));
		for(auto v:ss[i])
			upd(rt[i],1,m,v.first,v.second,dep[i]);
	}
	dfs2(1,0);
	solve(rt[1],1,m,0);
	for(int i=1;i<=m;++i){
		if(nok[i]) printf("They have disappeared.\n");
		else printf("%lld\n",ans[i]);
	}
	return 0;
}

悄悄地放个链接

悄悄地放个链接