题解 P3233 【[HNOI2014]世界树】

C3H5ClO

2019-06-25 12:38:44

Solution

### 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]); } } ```