BZOJ 3991 [SDOI 2015] 寻宝游戏 / Acwing 355. 异象石

从第一天下午调到第二天下午……蒟蒻这么菜是有原因的。

题目链接

Acwing 355. 异象石

BZOJ 3991: [SDOI2015]寻宝游戏

Luogu P3320 [SDOI2015]寻宝游戏

set的用法——by 知足–常乐

注意开long long ！！！

#include
using namespace std;typedef long long ll;
const int maxn=100100;
int n,cnt,tim,m;
int head[maxn],f[maxn][35],dfn[maxn];
ll dist[maxn],dep[maxn];struct node
{int id,ts;char c;bool operator <(const node a) const {return ts<a.ts;}
};set<node>s;struct edge
{int v,nxt,w;
}e[maxn<<1];void add(int u,int v,int w)
{e[++cnt].nxt=head[u];e[cnt].v=v;e[cnt].w=w;head[u]=cnt;
}void dfs(int u,int fa)
{dfn[u]=++tim;dep[u]=dep[fa]+1;for(int i=1;(1<<i)<=dep[u];i++){f[u][i]=f[f[u][i-1]][i-1];}for(int i=head[u];i;i=e[i].nxt){int v=e[i].v,w=e[i].w;if(v==fa) continue;f[v][0]=u;dist[v]=dist[u]+w;dfs(v,u);}
}int lca(int x,int y)
{if(dep[x]<dep[y]) swap(x,y);for(int i=30;i>=0;i--){if(dep[f[x][i]]>=dep[y]) x=f[x][i];}if(x==y) return x;for(int i=30;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}return f[x][0];
}node getp(set<node>::iterator x)
{if(x==s.begin()) return (*(--s.end()));return *(--x);
}node getn(set<node>::iterator x)
{if(x==--s.end()) return *(s.begin());return *(++x);
}ll dis(int x,int y)//树上差分求两点间距离
{return (ll)dist[x]+dist[y]-2*dist[lca(x,y)];
}int main()
{//freopen("input.txt","r",stdin);scanf("%d",&n);char ch;int x,y,z,st,t;for(int i=1;i<n;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}ll ans=0;dfs(1,0);scanf("%d",&m);for(int i=1;i<=m;i++){do{ch=getchar();}while(ch!='+'&&ch!='?'&&ch!='-');if(ch=='?'){printf("%lld\n",ans/2);continue;}scanf("%d",&y);if(ch=='+') {s.insert((node){y,dfn[y]});set <node> :: iterator  it=s.find((node){y,dfn[y]});int pre=(getp(it)).id;//dfn小于该点的第一个节点int nxt=(getn(it)).id;//dfn大于该点的第一个节点ans+=dis(((node)*it).id,pre)+dis(((node)*it).id,nxt)-dis(pre,nxt);}else if(ch=='-'){s.insert((node){y,dfn[y]});set <node> :: iterator  it=s.find((node){y,dfn[y]});int pre=(getp(it)).id;int nxt=(getn(it)).id;ans-=dis(((node)*it).id,pre)+dis(((node)*it).id,nxt)-dis(pre,nxt);s.erase(it);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！