传送门：>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 = 100010; const int MAXM = 27010; const int INF = 1061109567; inline int read(){ int x = 0; int w = 1; register int c = getchar(); while(c ^ ‘-‘ && (c < ‘0‘ || c > ‘9‘)) c = getchar(); if(c == ‘-‘) w = -1, c = getchar(); while(c >= ‘0‘ && c <= ‘9‘) x = (x << 3) + (x << 1) + c - ‘0‘, 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<<1],nxt[MAXN<<1],to[MAXN<<1],cost[MAXN<<1],num_edge; int dfn[MAXN],dep[MAXN],dis[MAXN],f[MAXN][30],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][0] = _f; for(int i = 1; (1<<i) <= dep[u]; ++i){ f[u][i] = f[f[u][i-1]][i-1]; } 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+1); } } inline int LCA(int a, int b){ if(dep[a] < dep[b]) swap(a, b); for(int i = 25; i >= 0; --i){ if(dep[a] - (1<<i) < dep[b]) continue; a = f[a][i]; } if(a == b) return a; for(int i = 25; i >= 0; --i){ if(f[a][i] == f[b][i]) continue; a = f[a][i], b = f[b][i]; } return f[a][0]; } int main(){ // freopen(".in","r",stdin); N = r, M = r; for(int i = 1; i < N; ++i){ x = r, y = r, w = r; add(x, y, w); add(y, x, w); } DFS(1, 0, 1); while(M--){ x = r; if(qxz.size() == 0){ val[x] = 1; qxz.insert((BaoZang){dfn[x],x}); printf("0\n"); continue; } if(!val[x]){ val[x] = 1; 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] - 2 * dis[LCA(it->i, it2->i)]; ans += dis[it->i] + dis[x] - 2 * dis[LCA(it->i, x)]; ans += dis[x] + dis[it2->i] - 2 * dis[LCA(x, it2->i)]; qxz.insert((BaoZang){dfn[x], x}); } else{ val[x] = 0; 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] - 2 * dis[LCA(it->i, it2->i)]; ans -= dis[it->i] + dis[x] - 2 * dis[LCA(it->i, x)]; ans -= dis[x] + dis[it2->i] - 2 * dis[LCA(x, it2->i)]; qxz.erase((BaoZang){dfn[x], x}); } printf("%d\n", ans); } return 0; }
原文：https://www.cnblogs.com/qixingzhi/p/9461963.html