题解 P3233 【[HNOI2014]世界树】
C3H5ClO
2019-06-25 12:38:44
### UPDATE:修复了题解代码复制错的错误
我来说一个很妙的方法,乱七八糟的细节比较少,DP方程也很简单。
先预处理出每个点深度,子树大小,距离最近的议事处编号及距离,这些东西其他dalao们已经说过了。
把每个议事处看做一种颜色,从虚树根开始DFS,给原树上每个节点染色。
一开始先把所有节点都染成虚树根节点所属议事处的颜色。
DFS时,若一条虚树边上父亲和儿子所属议事处不同,则倍增出原树上两议事处管理区域的分界处(即中点,注意“如果有多个临时议事处到该聚居地的距离一样,取其中编号最小的临时议事处”这个细节),然后把分界处及其子树再染成虚树上当前儿子所属议事处的颜色,最后递归,继续DFS。
这样说大家可能还不明白,我用样例第4个点举个栗子。
## 这是原树,加粗的点为议事处
![](https://cdn.luogu.com.cn/upload/pic/61379.png)
## 一开始用虚树根所属议事处给所有点染色后
![](https://cdn.luogu.com.cn/upload/pic/61380.png)
## 在虚树边1--3上,2号节点由3号管理,2号节点及其子树用3号节点染色后
![](https://cdn.luogu.com.cn/upload/pic/61381.png)
## 7号节点染色后
![](https://cdn.luogu.com.cn/upload/pic/61382.png)
## 8号节点染色后
![](https://cdn.luogu.com.cn/upload/pic/61383.png)
对于每个议事处,记录染成它的颜色的节点的个数,由于每次染色只会覆盖一种颜色(即父亲与儿子所属议事处不同时父亲所属议事处的颜色),因此每次染色时只要被覆盖的颜色的节点个数减掉本次染色节点数,本次染色的颜色的节点个数加上本次染色节点数就可以了。
上个代码,辅助理解。
```cpp
void dfs3(int x)
{
/*
g[x].first表示离最近议事处的距离,second表示最近议事处的编号,
f[i][j]用于倍增,ans[x]表示当前染成x号议事处颜色的点的个数
*/
int u=g[x].second,v;
for(ri i=head2[x];i;i=nxt2[i])
{
y=to2[i];
v=g[y].second;
if(u!=v)
{
d=dep[v]-(getdis(u,v)-(u<v))/2;
for(ri j=LO;j>=0;j--)
if(dep[f[j][y]]>=d)y=f[j][y];
ans[u]-=siz[y];
ans[v]+=siz[y];
}
dfs3(to2[i]);
}
}
```
还是没搞懂就看看完整代码吧。
```cpp
#include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
#define ri register int
#define pii pair<int,int>
const int INF=987654321;
int dfin[300005],dfout[300005],dep[300005],siz[300005],f[19][300005],now,len,ans[300005];
int n,x,y,q,m,h[300005],LO,a[300005],b[600005],cnt,sta[300005],top,f1[300005],d,minus[300005];
bool bo[300005];
pii g[300005];
int head[300005],to[600005],nxt[600005],ecnt,head2[300005],to2[600005],nxt2[600005],ecnt2;
void add(int x,int y)
{
ecnt++;
to[ecnt]=y;
nxt[ecnt]=head[x];
head[x]=ecnt;
}
void add2(int x,int y)
{
ecnt2++;
to2[ecnt2]=y;
nxt2[ecnt2]=head2[x];
head2[x]=ecnt2;
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(ri i=LO;i>=0;i--)
if(dep[f[i][x]]>=dep[y])x=f[i][x];
if(x==y)return x;
for(ri i=LO;i>=0;i--)
if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y];
return f[0][x];
}
int getdis(int x,int y)
{
return dep[x]+dep[y]-2*dep[lca(x,y)];
}
void dfs0(int x)
{
siz[x]=1;
dfin[x]=++now;
for(ri i=head[x];i;i=nxt[i])
if(!dfin[to[i]])
{
dep[to[i]]=dep[x]+1;
f[0][to[i]]=x;
dfs0(to[i]);
siz[x]+=siz[to[i]];
}
dfout[x]=++now;
}
void dfs1(int x)
{
if(bo[x])g[x]=pii(0,x);
else g[x]=pii(INF,0);
for(ri i=head2[x];i;i=nxt2[i])
{
dfs1(to2[i]);
if(g[x]>pii(g[to2[i]].first+dep[to2[i]]-dep[x],g[to2[i]].second))
g[x]=pii(g[to2[i]].first+dep[to2[i]]-dep[x],g[to2[i]].second);
}
}
void dfs2(int x)
{
for(ri i=head2[x];i;i=nxt2[i])
{
if(g[to2[i]]>pii(g[x].first+dep[to2[i]]-dep[x],g[x].second))
g[to2[i]]=pii(g[x].first+dep[to2[i]]-dep[x],g[x].second);
dfs2(to2[i]);
}
}/*
void dfs3(int x)
{
if(x==b[1])minus[x]-=siz[1]-siz[b[1]];
for(ri i=head2[x];i;i=nxt2[i])
{
dfs3(to2[i]);
if(g[to2[i]].second!=g[x].second)minus[x]+=siz[to2[i]];
else minus[x]+=minus[to2[i]];
}
ans[g[x].second]=siz[x]-minus[x];
}*/
void dfs4(int x)
{
int u=g[x].second,v;
for(ri i=head2[x];i;i=nxt2[i])
{
y=to2[i];
v=g[y].second;
if(u!=v)
{
d=dep[v]-(getdis(u,v)-(u<v))/2;
for(ri j=LO;j>=0;j--)
if(dep[f[j][y]]>=d)y=f[j][y];
ans[u]-=siz[y];
ans[v]+=siz[y];
}
dfs4(to2[i]);
}
}
void dfs5(int x)
{
for(ri i=head2[x];i;i=nxt2[i])dfs5(to2[i]);
minus[x]=ans[x]=head2[x]=bo[x]=0;
}
bool cmp1(int x,int y)
{
return dfin[x]<dfin[y];
}
bool cmp2(int x,int y)
{
return (x>0?dfin[x]:dfout[-x])<(y>0?dfin[y]:dfout[-y]);
}
int main()
{
scanf("%d",&n);
LO=floor(log2(n-1));
for(ri i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dep[1]=1;
dfs0(1);
for(ri i=1;i<=LO;i++)
for(ri j=1;j<=n;j++)
f[i][j]=f[i-1][f[i-1][j]];
scanf("%d",&q);
for(ri i=1;i<=q;i++)
{
scanf("%d",&m);
for(ri j=1;j<=m;j++)
{
scanf("%d",h+j);
bo[h[j]]=1;
a[j]=h[j];
}
sort(a+1,a+m+1,cmp1);
cnt=0;
b[++cnt]=a[1];
b[++cnt]=-a[1];
for(ri j=2;j<=m;j++)
{
x=lca(a[j-1],a[j]);
b[++cnt]=x;
b[++cnt]=-x;
b[++cnt]=a[j];
b[++cnt]=-a[j];
}
sort(b+1,b+cnt+1,cmp2);
len=0;
for(ri j=1;j<=cnt;j++)
if(b[j]!=b[j-1])b[++len]=b[j];
for(ri j=1;j<=len;j++)
{
if(b[j]>0)sta[++top]=b[j];
else add2(sta[top-1],sta[top]),top--;
}
dfs1(b[1]);
dfs2(b[1]);
//dfs3(b[1]);
ans[g[b[1]].second]=siz[1];
//for(ri j=1;j<=n;j++)printf("%d ",ans[j]); putchar('\n');
dfs4(b[1]);
for(ri j=1;j<=m;j++)printf("%d ",ans[h[j]]); putchar('\n');
dfs5(b[1]);
}
}
```