题解 P3233 【[HNOI2014]世界树】
xukuan
2020-05-04 18:39:28
我来讲一下这题虚树的建法
1. 把所有会议室的点按根节点最小的$dfn$序排序，求出任意两点的$LCA$
2. 把所有LCA的点和会议室的点及其相反数加进去，按$dfn$序（正的正序，负的倒序）排序之后$unique$
3. 然后如果点的值$>0$进栈，$<0$连边然后出栈。
4. 然后$dp$，第$1$遍$dfs$求深度和两个$dfn$序，第$2$遍和第$3$遍求距离和编号的最小值，第$4$编统计答案
~~代码贺了我们班大佬ckh的代码~~
```cpp
//自行加火车头
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
#define prll pair<ll,ll>
#define mkpr make_pair
using namespace std;
const ll N=300010,INF=1ll<<30;
ll n,m,cnt,top,a[N],b[N<<1],h[N],ans[N],d[N],size[N],p[N][30],v[N],st[N],dfnin[N],dfnout[N];
ll ver[N<<1],Next[N<<1],head[N],tot;
ll _ver[N<<1],_Next[N<<1],_head[N],_tot;
prll g[N];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
ll y=10,len=1;
while(y<=x){
y=(y<<3)+(y<<1);
len++;
}
while(len--){
y/=10;
putchar(x/y+48);
x%=y;
}
}
inline void addEdge(ll x,ll y){
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
inline void _addEdge(ll x,ll y){
_ver[++_tot]=y;
_Next[_tot]=_head[x];
_head[x]=_tot;
}
void dfs1(ll x,ll before){
d[x]=d[before]+1; size[x]=1; dfnin[x]=++cnt;
p[x][0]=before; for(ll i=1; i<=20; i++) p[x][i]=p[p[x][i-1]][i-1];
for(ll i=head[x]; i; i=Next[i]){
ll y=ver[i];
if(y==before) continue;
dfs1(y,x);
size[x]+=size[y];
}
dfnout[x]=++cnt;
}
void dfs2(ll x){
if(v[x]) g[x]=mkpr(0,x);
else g[x]=mkpr(INF,0);
for(ll i=_head[x]; i; i=_Next[i]){
ll y=_ver[i];
dfs2(y);
g[x]=min(g[x],mkpr(g[y].first+d[y]-d[x],g[y].second));
}
}
void dfs3(ll x){
for(ll i=_head[x]; i; i=_Next[i]){
ll y=_ver[i];
g[y]=min(g[y],mkpr(g[x].first+d[y]-d[x],g[x].second));
dfs3(y);
}
}
inline ll LCA(ll x,ll y){
if(d[x]>d[y]) swap(x,y);
for(ll i=20; i>=0; i--){
if(d[x]<=d[p[y][i]]) y=p[y][i];
}
if(x!=y){
for(ll i=20; i>=0; i--){
if(p[x][i]!=p[y][i]){
x=p[x][i];
y=p[y][i];
}
}
return p[x][0];
}
return x;
}
inline ll getdis(ll x,ll y){
return d[x]+d[y]-2*d[LCA(x,y)];
}
void dfs4(ll x){
ll u=g[x].second;
for(ll i=_head[x]; i; i=_Next[i]){
ll y=_ver[i],v=g[y].second;
if(u!=v){
ll dis=d[v]-(getdis(u,v)-(u<v))/2;
for(ll j=20; j>=0; j--){
if(d[p[y][j]]>=dis) y=p[y][j];
}
ans[u]-=size[y]; ans[v]+=size[y];
}
dfs4(_ver[i]);
}
}
void clean(ll x){
for(ll i=_head[x]; i; i=_Next[i]) clean(_ver[i]);
ans[x]=_head[x]=v[x]=0;
}
inline bool cmp1(ll x,ll y){
return dfnin[x]<dfnin[y];
}
inline bool cmp2(ll x,ll y){
return (x>0?dfnin[x]:dfnout[-x])<(y>0?dfnin[y]:dfnout[-y]);
}
int main(){
n=read();
for(ll i=1; i<n; i++){
ll x=read(),y=read();
addEdge(x,y);
addEdge(y,x);
}
dfs1(1,0);
for(ll T=read(); T; T--){
m=read();
for(ll i=1; i<=m; i++){
h[i]=a[i]=read();
v[a[i]]=1;
}
sort(a+1,a+1+m,cmp1);
cnt=0;
b[++cnt]=a[1]; b[++cnt]=-a[1];
for(ll i=2; i<=m; i++){
ll root=LCA(a[i-1],a[i]);
b[++cnt]=root; b[++cnt]=-root;
b[++cnt]=a[i]; b[++cnt]=-a[i];
}
sort(b+1,b+1+cnt,cmp2);
cnt=unique(b+1,b+1+cnt)-b-1;
for(ll i=1; i<=cnt; i++){
if(b[i]>0) st[++top]=b[i];
else{
_addEdge(st[top-1],st[top]);
st[top--]=0;
}
}
dfs2(b[1]); dfs3(b[1]);
ans[g[b[1]].second]=size[1];
dfs4(b[1]);
for(ll i=1; i<=m; i++){
write(ans[h[i]]);
putchar(' ');
}
putchar('\n');
clean(b[1]);
}
return 0;
}
```