萌新求调小清新数据结构,wa在#21
  • 板块P4115 Qtree4
  • 楼主qzmoot
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/11/7 17:06
  • 上次更新2024/11/7 20:16:10
查看原帖
萌新求调小清新数据结构,wa在#21
774854
qzmoot楼主2024/11/7 17:06
#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N=1e5+5,inf=1e18;
template<typename T>
inline void rd(T& x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9')x=x*10+ch-48,ch=getchar(); 
	x*=f;
}
template<typename T,typename ...Args>
inline void rd(T& x,Args& ...args)
{
	rd(x),rd(args...);
}
template<typename T>
inline void wr(T x)
{
	if(x<=9)
		putchar(x+48);
	else
		wr(x/10),putchar(x%10+48);
}
template<typename T>
inline void wrln(T x)
{
	wr(x),putchar('\n');
}
int n,m,a[N],cnt;
int rt,tot;
int siz[N],maxp[N];
bitset<N>vis;
vector<pii>e[N];
int fa[N];
namespace TreeCut
{
	int fa[N],siz[N],top[N],son[N],dep[N],dep2[N];
	inline void dfs1(int u,int fr)
	{
		fa[u]=fr;
		siz[u]=1;
		dep[u]=dep[fr]+1;
		int maxson=-1;
		for(auto v:e[u])
		{
			if(v.fi==fr)
				continue;
			dep2[v.fi]=dep2[u]+v.se;
			dfs1(v.fi,u);
			siz[u]+=siz[v.fi];
			if(maxson<siz[v.fi])
				maxson=siz[v.fi],son[u]=v.fi;
		}
	}
	inline void dfs2(int u,int tp)
	{
		top[u]=tp;
		for(auto v:e[u])
		{
			if(v.fi==fa[u])
				continue;
			if(v.fi==son[u])
				dfs2(v.fi,tp);
			else
				dfs2(v.fi,v.fi);
		}
	}
	inline void init()
	{
		dfs1(1,0);
		dfs2(1,1);
	}
	inline int lca(int x,int y)
	{
		while(top[x]!=top[y])
		{
			if(dep[top[x]]<dep[top[y]])
				swap(x,y);
			x=fa[top[x]];
		}
		return dep[x]<dep[y]?x:y;
	}
	inline int dis(int x,int y)
	{
		return dep2[x]+dep2[y]-(dep2[lca(x,y)]<<1);
	}
}
void find_w(int u,int fa)
{
	siz[u]=1;
	maxp[u]=0;
	for(auto v:e[u])
	{
		if(v.fi==fa || vis[v.fi])
			continue;
		find_w(v.fi,u);
		siz[u]+=siz[v.fi];
		maxp[u]=max(maxp[u],siz[v.fi]);
	}
	maxp[u]=max(maxp[u],tot-siz[u]);
	if(maxp[u]<maxp[rt])
		rt=u;
}
struct heap{
	priority_queue<int>q,d;
	inline int size()
	{
		return q.size()-d.size();
	}
	inline void insert(int x)
	{
		q.push(x);
	}
	inline void del(int x)
	{
		d.push(x);
	}
	inline int top()
	{
		if(!size())
			return -inf;
		while(d.size() && q.top()==d.top())
			q.pop(),d.pop();
		return q.top();
	}
	inline int ask()
	{
		if(size()<2)
			return -inf;
		int x=top(),y;
		del(x);
		y=top();
		insert(x);
		return x+y;
	}
}all,t1[N],t2[N];
void calc(int u,int fa,int ds)
{
	t1[rt].insert(ds);
	for(auto v:e[u])
	{
		if(vis[v.fi] || v.fi==fa)
			continue;
		calc(v.fi,u,ds+v.se);
	}
}
void solve(int u,int fr)
{
	vis[u]=1;
	fa[u]=fr;
	for(auto v:e[u])
	{
		if(vis[v.fi])
			continue;
		tot=siz[v.fi];
		maxp[rt=0]=inf;
		find_w(v.fi,0);
		calc(v.fi,u,v.se);
		t2[u].insert(t1[rt].top());
		solve(rt,u);
	}
	t2[u].insert(0);
	all.insert(t2[u].ask());
}
void add(int u)
{
	cnt++;
	all.del(t2[u].ask());
	t2[u].insert(0);
	all.insert(t2[u].ask());
	int i=u;
	while(fa[i])
	{
		int fr=fa[i];
		int len=TreeCut::dis(u,fr);
		all.del(t2[fr].ask());
		if(t1[i].size())
			t2[fr].del(t1[i].top());
		t1[i].insert(len);
		if(t1[i].size())
			t2[fr].insert(t1[i].top());
		all.insert(t2[fr].ask());
		i=fa[i];
	}
}
void del(int u)
{
	cnt--;
	all.del(t2[u].ask());
	t2[u].del(0);
	all.insert(t2[u].ask());
	int i=u;
	while(fa[i])
	{
		int fr=fa[i];
		int len=TreeCut::dis(fr,u);
		all.del(t2[fr].ask());
		if(t1[i].size())
			t2[fr].del(t1[i].top());
		t1[i].del(len);
		if(t1[i].size())
			t2[fr].insert(t1[i].top());
		all.insert(t2[fr].ask());
		i=fa[i];
	}
}
void upd(int u)
{
	if(!a[u])
		del(u),a[u]=1;
	else
		add(u),a[u]=0;
}
int query()
{
	return max(0ll,all.top());
}
signed main()
{
	rd(n);
	cnt=n;
	for(int i=1,u,v,w;i<n;i++)
	{
		rd(u,v,w);
		e[u].pb(mp(v,w));
		e[v].pb(mp(u,w)); 
	}
	TreeCut::init();
	maxp[rt=0]=tot=n;
	find_w(1,0);
	solve(rt,0);
	rd(m);
	while(m--)
	{
		char op=getchar();
		while(op==' ' || op=='\n' || op=='r')
			op=getchar();
		if(op=='C')
		{
			int x;
			rd(x);
			upd(x);
		}
		else
		{
			if(!cnt)
				puts("They have disappeared.");
			else
				wrln(cnt==1?0:query());
		}
	}
	return 0;
}
2024/11/7 17:06
加载中...