虚树-学习笔记
i207M
2018-08-23 14:41:58
# 实现细节：
不要认为虚树上所有点都满足给出的点集的性质，**因为有附加的LCA！**，注意区分它们！
不要认为虚树上所有点都满足给出的点集的性质，**因为有附加的LCA！**，注意区分它们！
不要认为虚树上所有点都满足给出的点集的性质，**因为有附加的LCA！**，注意区分它们！
## BZOJ 3743
~~这个题想想也不难，但是还是被卡了很久，主要是边权×2那里~~
一颗树n个点，n-1条边，经过每条边都要花费一定的时间，任意两个点都是联通的。
有K个人（分布在K个不同的点）要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发，把这K个人分别送回去。
请你回答，对于i=1~n，如果在第i个点举行聚会，司机最少需要多少时间把K个人都送回家。K <= N <= 500000
------------
首先，对于没有被标记的点，一部分是没有用处的，因为它们不在两两标记点的路径上，我们不用考虑它；
所以我们可以建立一棵虚树，虚树上保留的点是，标记点或标记点路径上的点；
建立方法是从一个**标记点**出发，遍历整棵树，如果一个点及其子树内有标记点，那么它就可以保留；
**虚树的叶子节点一定是标记点**
这样，**对于虚树上的点，遍历整棵树并回到原点的距离一定是整个虚树的边权和×2**，因为每条边都要遍历两次；如果不用回到原点，它就可以留在距离最远的叶子里，这个点一定是直径的端点，几次DFS就好；
对于虚树外的点，最优方案一定是先走最近的路径到虚树上，处理每个点到虚树的距离；
```
#define N 500010
#define M N<<1
#define int ll
int v[M], nx[M], w[M];
int cnt, head[N];
il void add(int uu, int vv, int ww)
{
v[++cnt] = vv, w[cnt] = ww, nx[cnt] = head[uu];
head[uu] = cnt;
}
int dis[N];
int sz[N];
int sum;
int n, k;
int mxd, mxk;
void dfs(int x, int f)
{
for (ri i = head[x]; i; i = nx[i])
{
if (v[i] == f) continue;
dfs(v[i], x);
sz[x] += sz[v[i]];
}
}
int top[N];
void efs(int x, int f, int d)
{
if (top[x] == x)
{
if (mxd < d)
{
mxd = d;
mxk = x;
}
}
for (ri i = head[x]; i; i = nx[i])
{
if (v[i] == f) continue;
if (sz[v[i]])
{
sum += w[i];
top[v[i]] = v[i];
efs(v[i], x, d + w[i]);
}
else
{
dis[v[i]] = dis[x] + w[i];
top[v[i]] = top[x];
efs(v[i], x, d + w[i]);
}
}
}
int len[N];
void ffs(int x, int f, int d)
{
len[x] = max(d, len[x]);
if (mxd < d)
{
mxd = d;
mxk = x;
}
for (ri i = head[x]; i; i = nx[i])
{
if (v[i] == f) continue;
if (sz[v[i]])
ffs(v[i], x, d + w[i]);
}
}
signed main()
{
#ifdef M207
freopen("in.in", "r", stdin);
#endif
in(n), in(k);
if (n == 1)
{
puts("0");
return 0;
}
for (ri i = 1, a, b, c; i < n; ++i)
{
in(a), in(b), in(c);
add(a, b, c);
add(b, a, c);
}
int st = 1;
for (ri i = 1, t; i <= k; ++i)
{
in(t);
++sz[t];
st = t;
}
dfs(st, 0);
top[st] = st;
mxd = 0, mxk = st;
efs(st, 0, 0);
mxd = 0;
ffs(mxk, 0, 0);
mxd = 0;
ffs(mxk, 0, 0);
sum <<= 1;
for (ri i = 1; i <= n; ++i)
{
int ans = sum + dis[i] - len[top[i]];
printf("%lld\n", ans);
}
return 0;
}
```
------------
## 以下是真正的虚树
我们建立一棵虚树，只包括询问的点和它们的LCA
建树方法：我们的栈里其实维护的是到DFS到栈顶时，栈顶的祖先那条链。
[好博客](https://www.cnblogs.com/Michael-Li/p/8763242.html)
注意，下面的代码没有判断tp=0的情况。
```cpp
void ins(int x)
{
int f=lca(x,st[tp]);
while(tp>1&&dfn[f]<=dfn[st[tp-1]]) sn[st[tp-1]].pb(st[tp]),--tp;
if(dfn[f]<dfn[st[tp]]) sn[f].pb(st[tp--]);
if(f!=st[tp]) st[++tp]=f;
st[++tp]=x;
}
```
### [HNOI2014]世界树
~~留坑待填$\leftarrow $我去不敢想象在学虚树时摸掉的题被猫讲了~~
我们先两次DP求出虚树上每个点被哪个点覆盖。然后，我们对于虚树上的每条边$(p,x)$单独考虑：
如果它们的bel相同，相当于链上的所有点有同一个bel，我们在父亲处算贡献。
如果不同，我们可以找出bel的分界点，用倍增预处理链上除了这个儿子外的size之和，贡献答案。
调这道题调了半天，因为自己举的例子太水了，忽略了虚树上有新建的不能覆盖别人的节点。
```cpp
void gfs(int x,int p)
{
int d=dep[x]-dep[p];
if(p&&(rad[p]+d<rad[x]||(rad[p]+d==rad[x]&&bel[p]<bel[x])))
rad[x]=rad[p]+d,bel[x]=bel[p];
for(solid v:sn[x])
{
gfs(v,x);
si[x]+=si[v];
}
if(!p) ans[bel[x]]+=n-si[x];
else if(bel[x]!=bel[p])
{
int mid=rad[x]+rad[p]+d,t=((mid&1)||bel[x]<bel[p])?jump(x,mid/2-rad[x]):jump(x,mid/2-1-rad[x]);
ans[bel[x]]+=sz[x]-si[x]+t;
if(sz[x]-si[x]+t<0) out(x,p,fa[x][0],sz[x],si[x],t,sz[x]-si[x]+t);
si[x]=sz[x]+t;
}
}
```
例题：codechef sadpairs