30pts求助
  • 板块P10930 异象石
  • 楼主Z_AuTwT
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/28 13:53
  • 上次更新2024/9/28 16:09:11
查看原帖
30pts求助
663195
Z_AuTwT楼主2024/9/28 13:53
#include<bits/stdc++.h>
using namespace std;
#define int long long
int dep[300010],fa[300010][32];
set<int> st;
int n,m;
vector<pair<int,int> >G[100010];
void init(int x,int Fa,int deep){
    dep[x]=deep;
    fa[x][0]=Fa;
    for(int i=1;i<=30;i++){
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for(auto ed:G[x]){
        if(ed.first==Fa) continue;
        init(ed.first,x,deep+ed.second);
    }
}
int Find_lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=30;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=30;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int Ans;
int Get(int x,int y){
	return dep[x]+dep[y]-2*dep[Find_lca(x,y)];
}
int dfn[100010],pos[100010];
int Time;
void dfs(int x,int fa){
	dfn[x]=++Time;
	pos[Time]=x;
	for(auto ed:G[x]){
		if(ed.first==fa) continue;
		dfs(ed.first,x);
	}
}
main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		G[x].push_back(make_pair(y,z));
		G[y].push_back(make_pair(x,z));
	}
	init(1,0,0);
	dfs(1,0);
	cin>>m;
	for(int i=1;i<=m;i++){
		char opt;
		cin>>opt;
		if(opt=='+'){
			int x;
			cin>>x;
			st.insert(dfn[x]);
			int Last,Next;
			auto dq=st.find(dfn[x]);
			if(dq==st.begin()) dq=st.end(),dq--;
			else dq--;
			Last=pos[*dq];
			if(++dq==st.end()) dq=st.begin();
			if(++dq==st.end()) dq=st.begin();
			Next=pos[*dq];
			Ans=Ans-Get(Last,Next)+Get(Last,x)+Get(x,Next);
		}else if(opt=='-'){
			int x;
			cin>>x;
			int Last,Next;
			auto dq=st.find(dfn[x]);
			if(dq==st.begin()) dq=st.end(),dq--;
			else dq--;
			Last=pos[*dq];
			if(++dq==st.end()) dq=st.begin();
			if(++dq==st.end()) dq=st.begin();
			Next=pos[*dq];
			if(dq==st.begin()) dq=st.end(),dq--;
			else dq--;
			Ans=Ans+Get(Last,Next)-Get(Last,x)-Get(x,Next);
			st.erase(dq);
		}else{
			cout<<Ans/2<<"\n";
		}
	}
}
2024/9/28 13:53
加载中...