寻宝游戏 bzoj-3991 SDOI-2015
题目大意：题目链接。
注释：略。
想法：我们发现如果给定了一些点有宝物的话那么答案就是树链的并。
树链的并的求法就是把所有点按照$dfs$序排序然后相加再减去相邻之间的$lca$。
故此我们按照$dfs$序维护一个平衡树。
每次往里插入节点即可。
实时用$lca$更新答案，复杂度$O(nlogn)$。
Code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define N 100010
using namespace std; typedef long long ll;
set<int>s;
int head[N],nxt[N<<1],to[N<<1],tot; ll val[N<<1];
ll dis[N],ans; int dic[N],f[22][N],size[N],re[N],dep[N],cnt;
bool vis[N];
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
ll rd() {ll x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
inline void add(int x,int y,ll z) {to[++tot]=y; val[tot]=z; nxt[tot]=head[x]; head[x]=tot;}
void dfs(int pos,int fa)
{
f[0][pos]=fa; for(int i=1;i<=20;i++) f[i][pos]=f[i-1][f[i-1][pos]];
dep[pos]=dep[fa]+1; dic[pos]=++cnt,re[cnt]=pos; size[pos]=1; for(int i=head[pos];i;i=nxt[i]) if(to[i]!=fa)
{
dis[to[i]]=dis[pos]+val[i]; dfs(to[i],pos); size[pos]+=size[to[i]];
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;~i;i--) if(dep[f[i][x]]>=dep[y]) x=f[i][x];
if(x==y) return x;
for(int i=20;~i;i--) if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
return f[0][x];
}
inline void output()
{
set<int>::iterator it=s.begin();
for(;it!=s.end();it++) printf("%d ",*it); puts("");
}
int main()
{
int n=rd(),m=rd(); for(int i=1;i<n;i++) {int x=rd(),y=rd(); ll z=rd(); add(x,y,z); add(y,x,z);}
dfs(1,1);
// for(int i=1;i<=n;i++) printf("%d %d %d %d %d %d
",re[dic[i]],dis[i],dic[i],dep[i],size[i],f[0][i]);
for(int i=1;i<=m;i++)
{
int x=rd();
if(s.empty()) {s.insert(dic[x]),ans=dis[x]; vis[x]=true;}
else if(!vis[x])
{
vis[x]=true;
set<int>::iterator it1=s.lower_bound(dic[x]);
set<int>::iterator it2=s.upper_bound(dic[x]);
if(it2==s.end())
{
it1--;
ans+=dis[x]-dis[lca(x,re[*it1])];
}
else
{
if(it1==s.begin()) ans+=dis[x]-dis[lca(x,re[*it1])];
else
{
it1--;
int y=re[*it1],z=re[*it2];
ans+=dis[x]+dis[lca(y,z)]-dis[lca(x,y)]-dis[lca(x,z)];
}
}
s.insert(dic[x]);
}
else
{
vis[x]=false;
set<int>::iterator it1=s.lower_bound(dic[x]);
set<int>::iterator it2=s.upper_bound(dic[x]);
if(it2==s.end())
{
if(it1==s.begin()) ans=0;
else
{
it1--;
int y=re[*it1];
ans+=dis[lca(x,y)]-dis[x];
}
}
else
{
if(it1==s.begin())
{
int z=re[*it2];
ans+=dis[lca(x,z)]-dis[x];
}
else
{
it1--;
int y=re[*it1],z=re[*it2];
ans+=dis[lca(y,x)]+dis[lca(x,z)]-dis[x]-dis[lca(y,z)];
}
}
s.erase(dic[x]);
}
// output();
// cout << ans << endl ;
set<int>::iterator it1=s.begin();
set<int>::iterator it2=s.end();
if(it1==it2) puts("0");
else
{
it2--;
if(it1==it2) puts("0");
else printf("%lld
",(ans-dis[lca(re[*it1],re[*it2])])*2);
}
}
return 0;
}
小结：好题啊好题啊。