传送门：>Here<
题意：给出一棵树（有边权），刚开始键值全部为0。每次对其中一个键值进行异或，问每一次修改之后：选择任意一个点出发走到所有为1的点再走回来的最短路
解题思路
由于N,M都是十万级别的，所以必须在线处理。很容易想到每次只需要对答案做出一点修改即可
考虑现在有$k$的节点有宝藏，那么假设他们共同在某一棵子树内，那么整棵树的其他部分根本不需要遍历到。因此我们需要找到这个子树的根，这个根就是目前所有节点的LCA。然后考虑从这个LCA出发开始走，总是会先走到DFS序较小的这样最优——因为DFS序比当前节点大只有两种情况：1.在当前节点的子树内 2.在当前节点的上面。对于第一种情况，显然可以免去走很多路，而对于第二种情况是无法避免的。
因此我们可以维护一个set，里面的元素是所有为1的点，并且按照DFS序从小到大排。为了让总路程最短，也就是让任意两个相邻的DFS序的元素之间的路程最短。因此我们的答案就是$Dis(set[1],set[2]) + Dis(set[2],set[3]) + ... + Dis(set[k-1],set[k]) + Dis(set[k],set[1])$。每一次插入一个元素，删除其相邻两点之间的$。事实上，由于从哪里出发要回到哪里，因此整个路径会形成一个环，所以从环上的任意一个点出发都是不会影响的。
每一次插入一个元素，删除其相邻两点之间的$Dis$，并且连接当前节点和相邻两个节点。删除同理。在set中可以采用lowerbound或者find函数。注意要特判边界情况
Code
如果lowerbound找到了end，意味着当前这个DFS是最大的，因此相邻的应该找打begin。找到start同理（昨天调试了两个小时……）
/*By DennyQi 2018.8.11*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <set>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int MAXN = ;
const int MAXM = ;
const int INF = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) + (x << ) + c - '', c = getchar(); return x * w;
}
struct BaoZang{
int d,i;
};
bool operator < (const BaoZang& a, const BaoZang& b){
return a.d < b.d;
}
int N,M,x,y,ans,dfs_clock,w;
int first[MAXN<<],nxt[MAXN<<],to[MAXN<<],cost[MAXN<<],num_edge;
int dfn[MAXN],dep[MAXN],dis[MAXN],f[MAXN][],val[MAXN];
set <BaoZang> qxz;
inline void add(int u, int v, int w){
to[++num_edge] = v;
cost[num_edge] = w;
nxt[num_edge] = first[u];
first[u] = num_edge;
}
void DFS(int u, int _f, int d){
dfn[u] = ++dfs_clock;
dep[u] = d;
f[u][] = _f;
for(int i = ; (<<i) <= dep[u]; ++i){
f[u][i] = f[f[u][i-]][i-];
}
int v;
for(int i = first[u]; i; i = nxt[i]){
if((v = to[i]) == _f) continue;
dis[v] = dis[u] + cost[i];
DFS(v, u, d+);
}
}
inline int LCA(int a, int b){
if(dep[a] < dep[b]) swap(a, b);
for(int i = ; i >= ; --i){
if(dep[a] - (<<i) < dep[b]) continue;
a = f[a][i];
}
if(a == b) return a;
for(int i = ; i >= ; --i){
if(f[a][i] == f[b][i]) continue;
a = f[a][i], b = f[b][i];
}
return f[a][];
}
int main(){
// freopen(".in","r",stdin);
N = r, M = r;
for(int i = ; i < N; ++i){
x = r, y = r, w = r;
add(x, y, w);
add(y, x, w);
}
DFS(, , );
while(M--){
x = r;
if(qxz.size() == ){
val[x] = ;
qxz.insert((BaoZang){dfn[x],x});
printf("0\n");
continue;
}
if(!val[x]){
val[x] = ;
set<BaoZang>::iterator it = qxz.lower_bound((BaoZang){dfn[x], x});
if(it == qxz.end()){
it = qxz.begin();
}
set<BaoZang>::iterator it2;
if(it2 == qxz.begin()){
it2 = qxz.end();
--it;
}
else{
it2 = --it; ++it;
}
ans -= dis[it->i] + dis[it2->i] - * dis[LCA(it->i, it2->i)];
ans += dis[it->i] + dis[x] - * dis[LCA(it->i, x)];
ans += dis[x] + dis[it2->i] - * dis[LCA(x, it2->i)];
qxz.insert((BaoZang){dfn[x], x});
}
else{
val[x] = ;
set<BaoZang>::iterator it = qxz.find((BaoZang){dfn[x], x});
set<BaoZang>::iterator it1,it2;
if(it == qxz.begin()){
it1 = --qxz.end();
it2 = ++it; --it;
}
else if(it == --qxz.end()){
it1 = --it; ++it;
it2 = qxz.begin();
}
else{
it1 = --it; ++it;
it2 = ++it; --it;
}
ans += dis[it->i] + dis[it2->i] - * dis[LCA(it->i, it2->i)];
ans -= dis[it->i] + dis[x] - * dis[LCA(it->i, x)];
ans -= dis[x] + dis[it2->i] - * dis[LCA(x, it2->i)];
qxz.erase((BaoZang){dfn[x], x});
}
printf("%d\n", ans);
}
return ;
}