期末考试结束祭！
在期末考试前最后一发的测试中，异象石作为第二道题目出现QAQ。虽然知道是LCA图论，但还是敲不出来QAQ。
花了两天竞赛课的时间搞懂（逃
异象石
(stone.pas/c/cpp)
题目描述
Adera 是 Microsoft 应用商店中的一款解谜游戏。
异象石是进入 Adera 中异时空的引导物，在 Adera 的异时空中有一张地图。这张地图上
有 N 个点，有 N-1 条双向边把它们连通起来。起初地图上没有任何异象石，在接下来的 M
个时刻中，每个时刻会发生以下三种类型的事件之一：
1. 地图的某个点上出现了异象石（已经出现的不会再次出现）；
2. 地图某个点上的异象石被摧毁（不会摧毁没有异象石的点）；
3. 向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。
请你作为玩家回答这些问题。
输入格式
第一行有一个整数 N，表示点的个数。
接下来 N-1 行每行三个整数 x,y,z，表示点 x 和 y 之间有一条长度为 z 的双向边。
第 N+1 行有一个正整数 M。
接下来 M 行每行是一个事件，事件是以下三种格式之一：
+ x 表示点 x 上出现了异象石
- x 表示点 x 上的异象石被摧毁
输出格式
对于每个？事件，输出一个整数表示答案。
样例输入
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
数据范围与约定
对于 30%的数据，1 ≤ n, m ≤ 1000。
对于另 20%的数据，地图是一条链，或者一朵菊花。
对于 100%的数据，1 ≤ n, m ≤ 105, 1 ≤ x, y ≤ n, x ≠ y, 1 ≤ z ≤ 109。
我们先来考虑简单的情况。处理出每个点到树根的距离d[]后，如果此时地图上有两个点，那么使它们联通所需的边集总长度最小即为
d[x]+d[y]-2*d[LCA(x,y)]
这也是树上两点路径的算法。QAQ。
静态的还好说，可是这里是动态维护的，中间既有可能新加石头，也可能移走石头。
我们再来看多个石头的情况。
假设黄色是异象石，那么我们要求的就是标红边的线。（从此处开始，对LCA（x,y）的叙述就是x,y两点的距离 ) 那么标红边的线就是
LCA(1,2)+LCA(2,3)+LCA(3,1)的1/2，LCA(1,2)+LCA(2,3)+LCA(3,1)即为寻宝游戏的答案。
也就是图中被红圈包围起来边权的1/2啦 QAQ。
画再复杂一点的图我们不难发现我们求得，答案就是相邻节点路径之和，头尾也算相邻。
因此我们可以预处理出欲求节点间的最近公共祖先的f数组，还有用倍增思想求出的dis[][]，dis[i][j]即为从i节点向上走2^j步的路径权值。
怎么处理相邻呢?这里可以用时间戳和dfs序解决，dfs一遍就可以求得。我们设v[]为时间戳，a[]为dfs序。
理解的话，就是v[i]为第i节点被访问的顺序，a[x]为时间戳为x的节点编号。
另外动态维护的时候可以用到set。对于这么一个高深的stl容器，蒟蒻当然要一番学习。set是一个有序集合，我们还可以利用它的迭代器
（注 ：迭代器可以理解成stl里的指针 用iterator声明）
另外我们在返回迭代器时返回的是指针，要真正的那个值就要“解除引用”， 即“ * ”符号
另外set集合里存的是时间戳。
这个地方思维有点混乱QAQ大家可以在代码里看注释，注释里写的很清楚（吧）。
code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
typedef long long ll;
const int MAXN=;
int y,tot,head[MAXN],n,m,t,f[MAXN][],visit[MAXN],a[MAXN];
ll ans,d[MAXN],dis[MAXN][];
struct node{
int to,next;
ll val;
}edge[*MAXN];
set<int> s;
typedef set<int>::iterator It;// 定义一个迭代器的简称
It it;//定义一个迭代器
void add(int x,int y,ll z)
{
edge[++tot].to=y;
edge[tot].val=z;
edge[tot].next=head[x];
head[x]=tot;
}
void bfs()
{
queue<int>q;
q.push();
d[]=;visit[]=;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if(!visit[y])
{
q.push(y);visit[y]=;
d[y]=d[x]+;
f[y][]=x,dis[y][]=edge[i].val;
for(int j=;j<=t;j++)
{//预处理出倍增思想的f数组和dis数组
f[y][j]=f[f[y][j-]][j-];
dis[y][j]=dis[f[y][j-]][j-]+dis[y][j-];
}
}
}
}
}
void dfs(int x)
{//求出时间戳和dfs序，visit[]此时的作用是时间戳，a[]的作用是dfs序
visit[x]=++tot;a[tot]=x;
for(int i=head[x];i;i=edge[i].next)
if(!visit[edge[i].to]) dfs(edge[i].to);
}
inline It L(It it)
{// s.end()返回集合中最大元素的下一个位置的迭代器
if(it==s.begin()) return --s.end();
return --it; //直接减即可 因为在没有insert()之前，新加入的异象石的左右相邻节点是相邻的！
}
inline It R(It it)
{
if(it==--s.end()) return s.begin();
return ++it;
}
ll LCA(int x,int y)
{
ll ans=;
if(d[x]>d[y]) swap(x,y);
for(int i=t;i>=;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>=;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][]+dis[y][];
}
int main()
{
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
scanf("%d",&n);t=log2(n)+;
for(int i=;i<=n-;i++)
{
int x=,y=;
ll z=;
scanf("%d%d%lld",&x,&y,&z);
add(x,y,z);
add(y,x,z); //建图
}
bfs();//预处理
memset(visit,,sizeof(visit)); tot=;//注意清零！ visit数组前后意义不一样了
dfs();
scanf("%d",&m);
for(int i=;i<=m;i++)
{
int x=;
char ch;
cin>>ch;
if(ch=='+')
{//改变一个异象石时 需要来考虑和它左边相邻的，右边相邻的
scanf("%d",&x);
if(s.size())
{
it=s.lower_bound(visit[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(visit[x]);//set里面存的是时间戳
}
if(ch=='-')
{//set中元素一定不为空
scanf("%d",&x);
it=s.find(visit[x]);
y=*L(it),it=R(it);//同理，找出他当前的左右相邻节点
ans-=LCA(x,a[y])+LCA(x,a[*it])-LCA(a[y],a[*it]);
s.erase(visit[x]);
}
if(ch=='?') printf("%lld\n",ans/);
}
return ;
}
寻宝游戏和这道题本质是一样的，只需稍加改动，无伤大雅。
code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
typedef long long ll;
const int MAXN=;
int y,tot,head[MAXN],n,m,t,f[MAXN][],visit[MAXN],a[MAXN];
ll ans,d[MAXN],dis[MAXN][];
struct node{
int to,next;
ll val;
}edge[*MAXN];
set<int> s;
typedef set<int>::iterator It;
It it;
void add(int x,int y,ll z)
{
edge[++tot].to=y;
edge[tot].val=z;
edge[tot].next=head[x];
head[x]=tot;
}
void bfs()
{
queue<int>q;
q.push();
d[]=;visit[]=;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if(!visit[y])
{
q.push(y);visit[y]=;
d[y]=d[x]+;
f[y][]=x,dis[y][]=edge[i].val;
for(int j=;j<=t;j++)
{
f[y][j]=f[f[y][j-]][j-];
dis[y][j]=dis[f[y][j-]][j-]+dis[y][j-];
}
}
}
}
}
void dfs(int x)
{
visit[x]=++tot;a[tot]=x;
for(int i=head[x];i;i=edge[i].next)
if(!visit[edge[i].to]) dfs(edge[i].to);
}
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;
}
ll LCA(int x,int y)
{
ll ans=;
if(d[x]>d[y]) swap(x,y);
for(int i=t;i>=;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>=;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][]+dis[y][];
}
int main()
{
scanf("%d%d",&n,&m);t=log2(n)+;
for(int i=;i<=n-;i++)
{
int x=,y=;
ll z=;
scanf("%d%d%lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
bfs();
memset(visit,,sizeof(visit)); tot=;
dfs();
for(int i=;i<=m;i++)
{
int x=;
scanf("%d",&x);
if(!s.count(visit[x]))
{
if(s.size())
{
it=s.lower_bound(visit[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(visit[x]);
}
else
{
it=s.find(visit[x]);
y=*L(it),it=R(it);
ans-=LCA(x,a[y])+LCA(x,a[*it])-LCA(a[y],a[*it]);
s.erase(visit[x]);
}
printf("%lld\n",ans);
}
return ;
}
这篇文章可以说是虎头蛇尾了！
end
*Update 2018929
蓦然回首 那人已在灯火阑珊处.