一道LCA
原题链接
先跑一边\(dfs\)，求出每个节点的时间戳，如果我们将有异象石的节点按时间戳从小到大的顺序排列，累加相邻两节点之间的距离（首尾相邻），会发现总和就是答案的两倍。
于是我们只需要维护这个按时间戳排序的有序数列和答案即可。
当插入一个新的节点\(u\)时，设插入位置的原有两节点为\(x,y\)，\(dis(x,y)\)表示两节点间的距离，那么只需要将答案减去\(dis(x,y)\)，再加上\(dis(x,u)+dis(u,y)\)即可，删除则类似。
而为了快速求\(dis(x,y)\)，我们可以先用\(dfs\)求出\(d[x]\)，表示从节点\(x\)到根的距离，于是\(dis(x,y)=d[x]+d[y]-2\times d[LCA(x,y)]\)，\(LCA\)使用倍增法求即可。
至于维护有序数列，我们可用\(C++\ STL\ set\)来维护。
不过因为我平时\(STL\)用的比较少，这题也是我第一次用\(set\)及迭代器，所以代码可能写的比较鬼畜（尤其是迭代器部分又臭又长）。。
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
struct dd {
int x, t;
bool operator < (const dd &b)const
{
return t < b.t;
}
};
dd o, X, Y;
int fi[N], ne[N << 1], di[N << 1], da[N << 1], f[N][18], de[N], ti[N], l, gn, T, n;
ll dis[N];
set<dd>S;
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c<'0' || c>'9'; c = getchar())
p |= c == '-';
for (; c >= '0'&&c <= '9'; c = getchar())
x = x * 10 + (c - '0');
return p ? -x : x;
}
inline int re_l()
{
char c = getchar();
for (; c != '+'&&c != '-'&&c != '?'; c = getchar());
return c == '+' ? 1 : (c == '-' ? 2 : 0);
}
inline void sw(int &x, int &y)
{
int z = x;
x = y;
y = z;
}
inline void add(int x, int y, int z)
{
di[++l] = y;
da[l] = z;
ne[l] = fi[x];
fi[x] = l;
}
void dfs(int x)
{
int i, y;
ti[x] = ++T;
for (i = 1; i <= gn; i++)
f[x][i] = f[f[x][i - 1]][i - 1];
for (i = fi[x]; i; i = ne[i])
{
y = di[i];
if (!de[y])
{
de[y] = de[x] + 1;
dis[y] = dis[x] + da[i];
f[y][0] = x;
dfs(y);
}
}
}
int lca(int x, int y)
{
int i;
if (de[x] > de[y])
sw(x, y);
for (i = gn; ~i; i--)
if (de[f[y][i]] >= de[x])
y = f[y][i];
if (!(x^y))
return x;
for (i = gn; ~i; i--)
if (f[x][i] ^ f[y][i])
{
x = f[x][i];
y = f[y][i];
}
return f[x][0];
}
ll calc(int x, int y)
{
return dis[x] + dis[y] - (dis[lca(x, y)] << 1);
}
int main()
{
int i, m, x, y, z, si = 0;
ll s = 0;
n = re();
gn = log2(n);
for (i = 1; i < n; i++)
{
x = re();
y = re();
z = re();
add(x, y, z);
add(y, x, z);
}
de[1] = 1;
dfs(1);
m = re();
for (i = 1; i <= m; i++)
{
x = re_l();
if (!x)
printf("%lld\n", s >> 1);
else
{
o.x = re();
o.t = ti[o.x];
if (!(x ^ 1))
{
if (!si)
{
S.insert(o);
si++;
continue;
}
if (!(si ^ 1))
{
S.insert(o);
si++;
set<dd>::iterator it = S.find(o);
it == --S.end() ? Y = *S.begin() : Y = *--S.end();
s += calc(o.x, Y.x) << 1;
continue;
}
si++;
S.insert(o);
set<dd>::iterator fk, it = S.find(o);
fk = it;
it == --S.end() ? Y = *S.begin() : Y = *++it;
fk == S.begin() ? X = *--S.end() : X = *--fk;
s -= calc(X.x, Y.x);
s += calc(X.x, o.x);
s += calc(Y.x, o.x);
}
else
{
if (!(si ^ 2) || !(si ^ 1))
{
si--;
s = 0;
S.erase(o);
continue;
}
si--;
set<dd>::iterator fk, it = S.find(o);
fk = it;
it == --S.end() ? Y = *S.begin() : Y = *++it;
fk == S.begin() ? X = *--S.end() : X = *--fk;
S.erase(o);
s -= calc(X.x, o.x);
s -= calc(Y.x, o.x);
s += calc(X.x, Y.x);
}
}
}
return 0;
}