1870H - Standard Graph Problem - CodeForces Solution

// LUOGU_RID: 125406281
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e12;
struct Edge{int u,v,w;}E[200010];
struct Merge_Heap
{
	int lc[200010],rc[200010],val[200010],d[200010],tag[200010];
	void push(int rt,int t){if(rt) tag[rt]+=t,val[rt]+=t;}
	void pushdown(int rt)
	{
		if(!tag[rt]) return;
		push(lc[rt],tag[rt]);push(rc[rt],tag[rt]);
		tag[rt]=0;
	}
	int merge(int x,int y)
	{
		if(!x || !y) return x+y;
		if(val[x]>val[y]) swap(x,y);
		pushdown(x);rc[x]=merge(rc[x],y);
		if(d[lc[x]]<d[rc[x]]) swap(lc[x],rc[x]);
		d[x]=d[rc[x]]+1;
		return x;
	}
}H;
int fa[400010],dfn[400010],idfn[400010],sz[400010],son[400010],top[400010],stk[200010],col[400010],ffa[400010],rt[400010],tot;
char op[5];
ll wei[400010];
struct node
{
	int c;ll s;
	node operator+(const node &a)const
	{
		node ans;ans.s=0;
		ans.c=min(c,a.c);
		if(c==ans.c) ans.s+=s;
		if(a.c==ans.c) ans.s+=a.s;
		return ans;
	}
};
struct Seg
{
	int tag[1100010];
	node val[1100010];
	void build(int rt,int l,int r)
	{
		if(l==r) return val[rt].s=wei[idfn[l]],void();
		int mid=(l+r)/2;
		build(rt*2,l,mid);build(rt*2+1,mid+1,r);
		val[rt]=val[rt*2]+val[rt*2+1];
	}
	void push(int rt,int t){tag[rt]+=t;val[rt].c+=t;}
	void pushdown(int rt)
	{
		if(!tag[rt]) return;
		push(rt*2,tag[rt]);push(rt*2+1,tag[rt]);
		tag[rt]=0;
	}
	void update(int rt,int l,int r,int x,int y,int z)
	{
		if(l>y || r<x) return;
		if(x<=l && r<=y) return push(rt,z);
		pushdown(rt);
		int mid=(l+r)/2;
		update(rt*2,l,mid,x,y,z);update(rt*2+1,mid+1,r,x,y,z);
		val[rt]=val[rt*2]+val[rt*2+1];
	}
}S;
vector<int> G[400010];
int getF(int x){return ffa[x]==x?x:ffa[x]=getF(ffa[x]);}
void dfs1(int u)
{
	sz[u]=1;
	for(int v:G[u])
	{
		dfs1(v);sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(int u)
{
	dfn[u]=++tot;idfn[tot]=u;
	if(u==son[fa[u]]) top[u]=top[fa[u]];
	else top[u]=u;
	if(son[u]) dfs2(son[u]);
	for(int v:G[u])
		if(v!=son[u]) dfs2(v);
}
int main()
{
	int n,m,q,x,cnt;
	cin>>n>>m>>q;cnt=n;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
		H.val[i]=E[i].w;
		rt[E[i].u]=H.merge(rt[E[i].u],i);
	}
	iota(ffa+1,ffa+n+1,1);
	for(int i=1;i<=n;i++)
	{
		if(col[i]) continue;
		int tp=0;stk[++tp]=i;
		while(1)
		{
			int u=stk[tp],v=getF(E[rt[u]].v);
			col[u]=i;wei[u]=H.val[rt[u]];
			if(!rt[u]){wei[u]=INF;break;}
			if(!col[v]){stk[++tp]=v;continue;}
			if(col[v]!=i) break;
			cnt++;ffa[cnt]=cnt;
			int w;
			do
			{
				w=stk[tp--];
				H.push(rt[w],-H.val[rt[w]]);H.pushdown(rt[w]);
				rt[w]=H.merge(H.lc[rt[w]],H.rc[rt[w]]);
				fa[w]=ffa[w]=cnt;
				rt[cnt]=H.merge(rt[cnt],rt[w]);
			}while(w!=v);
			stk[++tp]=cnt;
		}
	}
	n=cnt;
	for(int i=1;i<=n;i++)
		if(fa[i]) G[fa[i]].push_back(i);
	for(int i=1;i<=n;i++)
		if(!fa[i]) dfs1(i),dfs2(i);
	S.build(1,1,n);
	while(q--)
	{
		scanf("%s%d",op,&x);
		while(x)
		{
			S.update(1,1,n,dfn[top[x]],dfn[x],op[0]=='+'?1:-1);
			x=fa[top[x]];
		}
		node t=S.val[1];
		if(t.c) puts("0");
		else if(t.s<INF) printf("%lld\n",t.s);
		else puts("-1");
	}
	return 0;
}