题解：P10406 「SMOI-R1」Company

ran_qwq · 2024-05-05 22:27:25 · 题解

首先，假设将一个公司看成一个“大点”，则连接最后的“大树”每个点度数最多为 2，否则可以将一棵子树接到另一棵子树上，这样更优。

这里有两种情况：一是一条链，二是两条链通过一个公司连接在一起。

对于第一种情况，又有最顶是 1 号树、最底是 2 号树，和最顶是 2 号树、最底是 1 号树两种子情况。对于第一种子情况，选离 x 最远的节点，接上另外一棵子树的根节点，产生 dis(x,l) 的贡献（l 是选中的叶子节点）；3\sim n 只要接的都是距离最远的叶子节点就可以随便接；而 2 子树会产生 dis(1,y) 的贡献；再加上自己加的 n-1 条边使其相连。第二种子情况类似，取个最大值即可。

对于第二种情况，枚举“大树”的根 r，这样在 r 中的贡献会减去最大深度，加上最大叶子节点距离（类似树的直径的求法）。贪心取两者之差最大的。与第一种情况类似，但是还要加上 dis(1,x)+dis(1,y)。

讲的有点抽象，放个丑陋的代码：

int n,ans,mx1,mx2,mx3,x,y,d1[M],d2[M],mx[N],dmx[N]; vi G1[M],G2[M]; 
struct Tree {
    int m; vi dep,dep2; vector<vi> G;
    void dfs(int u,int fa=0) {for(int v:G[u]) if(v!=fa) dep[v]=dep[u]+1,dfs(v,u);}
    void rdfs(int u,int fa=0) {for(int v:G[u]) if(v!=fa) dep2[v]=dep2[u]+1,rdfs(v,u);}
}T[N];
void dfs1(int u,int fa=0) {for(int v:T[1].G[u]) if(v!=fa) {d1[v]=d1[u]+1; if(v!=1&&T[1].G[v].size()<=1) mx1=max(mx1,d1[v]); dfs1(v,u);}}
void dfs2(int u,int fa=0) {for(int v:T[2].G[u]) if(v!=fa) {d2[v]=d2[u]+1; if(v!=1&&T[2].G[v].size()<=1) mx2=max(mx2,d2[v]); dfs2(v,u);}}
void QwQ() {
    n=rd(),ans=n-1,mx3=-INF;
    for(int i=1;i<=n;i++) {
        T[i].m=rd(),T[i].G.resize(T[i].m+1),T[i].dep.resize(T[i].m+1),T[i].dep2.resize(T[i].m+1);
        for(int j=2,x;j<=T[i].m;j++) x=rd(),T[i].G[x].pb(j),T[i].G[j].pb(x);
    }
    x=rd(),y=rd(),dfs1(x),dfs2(y);
    for(int i=1,s;i<=n;i++) {
        T[i].dfs(1),s=-1;
        for(int j=2;j<=T[i].m;j++) if(T[i].dep[j]>=mx[i]&&T[i].G[j].size()==1) mx[i]=T[i].dep[j],s=j;
        if(i>2) ans+=mx[i];
        if(!~s) continue; T[i].rdfs(s);
        for(int j=2;j<=T[i].m;j++) if(T[i].G[j].size()==1) dmx[i]=max(dmx[i],T[i].dep2[j]);
    }
    for(int i=1;i<=n;i++) mx3=max(mx3,dmx[i]-mx[i]);
    wr(max(ans+max(d1[1]+mx2,d2[1]+mx1),mx3!=-INF?ans+mx3+d1[1]+d2[1]:0),"\n");
}