NC51256. 异象石
描述
输入描述
第一行有一个整数 N，表示点的个数。
接下来 N-1 行每行三个整数 x,y,z，表示点 x 和 y 之间有一条长度为 z 的双向边。
第 N+1 行有一个正整数 M。
接下来 M 行每行是一个事件，事件是以下三种格式之一：
+ x 表示点 x 上出现了异象石
- x 表示点 x 上的异象石被摧毁
? 表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。
输出描述
对于每个 ? 事件，输出一个整数表示答案。
示例1
输入:
6 1 2 1 1 3 5 4 1 7 4 5 3 6 4 2 10 + 3 + 1 ? + 6 ? + 5 ? - 6 - 3 ?
输出:
5 14 17 10
C++(g++ 7.5.0) 解法, 执行用时: 166ms, 内存消耗: 30460K, 提交时间: 2022-08-17 11:08:04
#include<bits/stdc++.h>
using namespace std;
typedef set<int>::iterator IT;
typedef long long ll;
const int N=1e5+10;
int fa[N][20],hd[N],tot,n,m,vis[N],dep[N],dfn[N],cnt,pos[N];
set<int>s;
ll dis[N][20],ans;
struct Edge{
int v,w,nx;
}e[N<<1];
void addedge(int u,int v,int w)
{
e[tot].v=v;
e[tot].w=w;
e[tot].nx=hd[u];
hd[u]=tot++;
}
void bfs()
{
queue<int>q;
q.push(1);vis[1]=1;dep[1]=1;
while(q.size())
{
int u=q.front();q.pop();
for(int i=hd[u];~i;i=e[i].nx)
{
int v=e[i].v;
if(vis[v])continue;
vis[v]=1;
dep[v]=dep[u]+1;
fa[v][0]=u;
dis[v][0]=e[i].w;
for(int j=1;j<20;j++)
{
fa[v][j]=fa[fa[v][j-1]][j-1];
dis[v][j]=dis[fa[v][j-1]][j-1]+dis[v][j-1];
}
q.push(v);
}
}
}
void dfs(int u)
{
dfn[u]=++cnt;pos[cnt]=u;
for(int i=hd[u];~i;i=e[i].nx)
{
int v=e[i].v;
if(!dfn[v])dfs(v);
}
}
ll lca(int u,int v)
{
ll ret=0;
if(dep[u]>dep[v])swap(u,v);
for(int i=19;i>=0;i--)if(dep[fa[v][i]]>=dep[u])ret+=dis[v][i],v=fa[v][i];
if(u==v)return ret;
for(int i=19;i>=0;i--)
if(fa[u][i]!=fa[v][i])ret+=dis[u][i]+dis[v][i],u=fa[u][i],v=fa[v][i];
return ret+dis[u][0]+dis[v][0];
}
IT L(IT it)
{
if(it==s.begin())return --s.end();
return --it;
}
IT R(IT it)
{
if(it==--s.end())return s.begin();
return ++it;
}
int main()
{
memset(hd,-1,sizeof(hd));
scanf("%d",&n);
int u,v,w;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w),addedge(v,u,w);
}
bfs();
dfs(1);
char com[5];
scanf("%d",&m);
IT it;
for(int i=1;i<=m;i++)
{
scanf("%s",com);
if(com[0]=='+')
{
scanf("%d",&u);
if(s.size())
{
it=s.lower_bound(dfn[u]);
if(it==s.end())it=s.begin();
v=*L(it);
ans+=lca(u,pos[v])+lca(u,pos[*it])-lca(pos[v],pos[*it]);
}
s.insert(dfn[u]);
}
else if(com[0]=='-')
{
scanf("%d",&u);
it=s.find(dfn[u]);
v=*L(it),it=R(it);
ans-=lca(u,pos[v])+lca(u,pos[*it])-lca(pos[v],pos[*it]);
s.erase(dfn[u]);
}
else printf("%lld\n",ans/2);
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 269ms, 内存消耗: 32732K, 提交时间: 2020-04-30 16:55:30
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<cmath>
using ll = long long;
using namespace std;
const int u=100010;
int f[u][20],a[u],d[u],v[u],ver[2*u],nxt[2*u],edge[2*u],head[u];
ll dis[u][20],ans;
int n,m,tot,t,i,j,x,y,z;
set<int> s;
typedef set<int>::iterator It;
It it;
queue<int> q;
char str[2];
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}
void bfs()
{
q.push(1),v[1]=1,d[1]=1;
while(q.size())
{
x=q.front(); q.pop();
for(i=head[x];i;i=nxt[i])
if(!v[y=ver[i]])
{
q.push(y); v[y]=1;
d[y]=d[x]+1;
f[y][0]=x,dis[y][0]=edge[i];
for(j=1;j<=t;j++)
{
f[y][j]=f[f[y][j-1]][j-1];
dis[y][j]=dis[f[y][j-1]][j-1]+dis[y][j-1];
}
}
}
}
ll lca(int x,int y)
{
ll ans=0;
if(d[x]>d[y]) swap(x,y);
for(int i=t;i>=0;i--)
if(d[f[y][i]]>=d[x]) ans+=dis[y][i],y=f[y][i];
if(x==y) return ans;
for(int i=t;i>=0;i--)
if(f[x][i]!=f[y][i]) ans+=dis[x][i]+dis[y][i],x=f[x][i],y=f[y][i];
return ans+dis[x][0]+dis[y][0];
}
void dfs(int x)
{
v[x]=++tot,a[tot]=x;
for(int i=head[x];i;i=nxt[i])
if(!v[ver[i]]) dfs(ver[i]);
}
inline It L(It it)
{
if(it==s.begin()) return --s.end();
return --it;
}
inline It R(It it)
{
if(it==--s.end()) return s.begin();
return ++it;
}
int main()
{
cin>>n;
t=(int)(log(n)/log(2)+0.1);
for(i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
bfs();
memset(v,0,sizeof(v)),tot=0;
dfs(1);
cin>>m;
for(i=1;i<=m;i++)
{
scanf("%s",str);
if(str[0]=='+')
{
scanf("%d",&x);
if(s.size())
{
it=s.lower_bound(v[x]);
if(it==s.end()) it=s.begin();
y=*L(it);
ans+=lca(x,a[y])+lca(x,a[*it])-lca(a[y],a[*it]);
}
s.insert(v[x]);
}
if(str[0]=='-')
{
scanf("%d",&x);
it=s.find(v[x]);
y=*L(it),it=R(it);
ans-=lca(x,a[y])+lca(x,a[*it])-lca(a[y],a[*it]);
s.erase(v[x]);
}
if(str[0]=='?') printf("%lld\n",ans/2);
}
return 0;
}
C++(clang++11) 解法, 执行用时: 227ms, 内存消耗: 16328K, 提交时间: 2020-12-03 21:45:51
#include<set>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
set<int> s;
typedef set<int>::iterator IT;
const int M=1e5+10,t=20;
int id[M],a[M],h[M],cnt=0;
int dep[M],f[M][t+1],len=0;
ll d[M];
struct bian{int y,gg;ll c;}b[M<<1];
void dfs(int x)
{
id[x]=++cnt;a[cnt]=x;
for(int i=h[x];i;i=b[i].gg)
{
int y=b[i].y;
if(f[x][0]==y)continue;
dep[y]=dep[x]+1;f[y][0]=x;
d[y]=d[x]+b[i].c;
for(int j=1;j<=t;j++)
f[y][j]=f[f[y][j-1]][j-1];
dfs(y);
}
}
void jh(int &x,int &y){x^=y;y^=x;x^=y;}
int lca(int x,int y)
{
if(dep[x]<dep[y])jh(x,y);
for(int i=t;i>=0;i--)
if(dep[f[x][i]]>=dep[y])x=f[x][i];
// printf("%lld\n",ans);
if(x==y)return x;
for(int i=t;i>=0;i--)
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[y][0];
}
void ins(int x,int y,ll c)
{
b[++len].y=y;b[len].c=c;
b[len].gg=h[x];h[x]=len;
}
inline IT lef(IT it)
{
if(it==s.begin())return --s.end();
return --it;
}
inline IT righ(IT it)
{
if(it==--s.end())return s.begin();
return ++it;
}
ll dist(int x,int y)
{
int fx=lca(x,y);
return d[x]+d[y]-2*d[fx];
}
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;ll c;scanf("%d %d %lld",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
dep[1]=1;d[1]=0;
dfs(1);
int m;
ll ans=0;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
char ss[3];int x;
scanf("%s",ss+1);
if(ss[1]=='?')printf("%lld\n",ans/2ll);
else if(ss[1]=='+')
{
scanf("%d",&x);
if(s.size())
{
IT it=s.lower_bound(id[x]);
if(it==s.end())it=s.begin();
int y=*lef(it);
ans+=dist(a[y],x)+dist(a[*it],x)-dist(a[y],a[*it]);
}
s.insert(id[x]);
}
else
{
scanf("%d",&x);
IT it=s.find(id[x]);
int y=*lef(it);it=righ(it);
ans-=dist(a[y],x)+dist(a[*it],x)-dist(a[*it],a[y]);
s.erase(id[x]);
}
}
return 0;
}