题解 P3320 【[SDOI2015]寻宝游戏】
zhouyuheng2003
2018-01-18 15:25:30
这一题的的标签有“虚树”，但是虚树？难道对于每一次操作都O（n）的树形dp吗，那复杂度就是O（nm）的了，显然会TLE。
不难证明，这一题从任意一个有宝藏的起点出发的答案都是等价的（因为要回到起点，所以路径相当于是一个环），那么答案是什么呢，其实就是dis(a[1],a[2])+dis(a[2],a[3])+···+dis(a[k-1],a[k])+dis(a[k],a[1])，k为当前有宝藏的村庄数，a数组存放着按dfs序排序过后的有宝藏的村庄，那么每一次加一个点只要在原基础上删掉它按dfs序的前一个点和后一个点的距离、加上自己与那两个点的距离就好了（注意边界情况，即dfs序是最小的或者是最大的），删除同理。
有宝藏的村庄用一个set维护就好了，一次操作复杂度O（logn），树上点之间的距离可以用树链剖分或者是倍增实现（这里用的是倍增）
下面的是AC代码：
```cpp
#include<cstdio>
#include<cctype>
namespace fast_IO
{
const int IN_LEN=10000000,OUT_LEN=10000000;
char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf;
char *lastin=ibuf+IN_LEN;
const char *lastout=ibuf+OUT_LEN-1;
inline char getchar_()
{
if(ih==lastin)lastin=ibuf+fread(ibuf,1,IN_LEN,stdin),ih=ibuf;
return (*ih++);
}
inline void putchar_(const char x)
{
if(ih==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;
*oh++=x;
}
inline void flush(){fwrite(obuf, 1, oh - obuf, stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long LL;
#define rg register
template <typename T> inline T max(const T a,const T b){return a>b?a:b;}
template <typename T> inline T min(const T a,const T b){return a<b?a:b;}
template <typename T> inline T abs(const T a){return a>0?a:-a;}
template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;}
template <typename T> inline T gcd(const T a,const T b){if(a%b==0)return b;return gcd(b,a%b);}
template <typename T> inline T square(const T x){return x*x;};
template <typename T> inline void read(T&x)
{
char cu=getchar();x=0;bool fla=0;
while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}
while(isdigit(cu))x=x*10+cu-'0',cu=getchar();
if(fla)x=-x;
}
template <typename T> void printe(const T x)
{
if(x>=10)printe(x/10);
putchar(x%10+'0');
}
template <typename T> inline void print(const T x)
{
if(x<0)putchar('-'),printe(-x);
else printe(x);
}
inline void judge()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
}
#include<algorithm>
#include<set>
const int maxn=250001,maxm=500001;
int bit[19];
int n,m,s;
int head[maxn],nxt[maxm],tow[maxm],vau[maxm],tmp=1;
int who[maxn][19],dep[maxn];
LL dis[maxn][19];
inline void addb(const int u,const int v,const int w)
{
tmp++;
nxt[tmp]=head[u];
head[u]=tmp;
tow[tmp]=v;
vau[tmp]=w;
}
int tid[maxn],tim;
inline void dfs(const int u)
{
tid[u]=++tim;
for(rg int i=head[u];i;i=nxt[i])
{
const int v=tow[i];
if(who[u][0]!=v)
{
who[v][0]=u;
dis[v][0]=vau[i];
dep[v]=dep[u]+1;
dfs(v);
}
}
}
inline LL dist(int a,int b)
{
rg LL ans=0;
if(dep[a]<dep[b])swap(a,b);
const int lenth=dep[a]-dep[b];
for(rg int i=0;bit[i]<=lenth;i++)
if(lenth&bit[i])
ans+=dis[a][i],a=who[a][i];
if(a==b)return ans;
for(rg int i=18;i>=0;i--)
if(who[a][i]!=who[b][i])
ans+=dis[a][i]+dis[b][i],a=who[a][i],b=who[b][i];
return ans+dis[a][0]+dis[b][0];
}
LL ans;
struct Node
{
int id;
bool operator <(const Node b)const
{
return tid[id]<tid[b.id];
}
};
std::set<Node>Q;
inline std::set<Node>::iterator last(std::set<Node>::iterator Pos)
{
if(Pos==Q.begin())Pos=Q.end();
Pos--;
return Pos;
}
inline std::set<Node>::iterator next(std::set<Node>::iterator Pos)
{
Pos++;
if(Pos==Q.end())Pos=Q.begin();
return Pos;
}
std::set<Node>::iterator Posl,Posr;
int main()
{
// judge();
bit[0]=1;
for(rg int i=1;i<=18;i++)bit[i]=bit[i-1]<<1;
read(n),read(m),s=1;
for(rg int i=1;i<n;i++)
{
int u,v,w;read(u),read(v),read(w);
addb(u,v,w),addb(v,u,w);
}
who[s][0]=s,dep[s]=1;
dfs(s);
for(rg int j=1;j<=18;j++)
for(rg int i=1;i<=n;i++)
who[i][j]=who[who[i][j-1]][j-1],dis[i][j]=dis[i][j-1]+dis[who[i][j-1]][j-1];
for(rg int i=1;i<=m;i++)
{
int u;read(u);
if(Q.find((Node){u})!=Q.end())
{
if(Q.size()!=1)
{
Posl=Posr=Q.find((Node){u});
Posl=last(Posl),Posr=next(Posr);
ans-=dist(u,(*Posl).id)+dist(u,(*Posr).id);
ans+=dist((*Posl).id,(*Posr).id);
}
Q.erase((Node){u});
}
else
{
Q.insert((Node){u});
if(Q.size()!=1)
{
Posl=Posr=Q.find((Node){u});
Posl=last(Posl),Posr=next(Posr);
ans+=dist(u,(*Posl).id)+dist(u,(*Posr).id);
ans-=dist((*Posl).id,(*Posr).id);
}
}
print(ans),putchar('\n');
}
return flush(),0;
}
```