[题解] SP6717 TWOPATHS - Two Paths

Alex_Eon · 2023-07-21 14:34:53 · 题解

\color{red}博客内食用效果更佳（点我）

题外话

SPOJ 太难用了，忘开 long long 调半天。

思路：换根 DP

复杂度：O(n)

题解中涉及到的变量：

主体思路

将题意转换为某一条边所连接的两棵树直径最大乘积，维护每个节点子树内外直径，答案就是最大乘积。

子树内直径来源：

• 从当前节点出发的最长链、次长链（now.dmx）拼接而成。
• 子节点子树中直径（now.d）。

子树外直径来源：

• 父节点子树外直径（fa.dia）。
• 从父节点出发，向父节点子树外延伸最长链（fa.umx）、父节点子树内不经过当前节点的最长链（fa.dmx）拼接而成。
• 父节点子树内，当前节点子树外直径：
  • 从父节点出发，父节点子树内不经过当前节点的最长链、次长链（fa.dmx）拼接而成。
  • 在父节点子树内，不经过父节点，不经过当前子树的最长链（fa.d）。

综上所述，为了取到一些在父节点子树内但不在当前子树内的信息，我们需要维护一些最长、次长、次次长链（d 的次次长维护不是必须的，在代码中顺便就维护了），转移时，只从子节点向父节点转移部分信息，保证查询时可以查到合法信息。

维护时，为了省去大量的 if，可以采用将最大、次大、次次大打包为小数据结构的方式，代码、调试难度较小。具体地，实现了以下功能：

• 插入一个值来更新当前已有值。
• 询问除去某个值后的最大值。
• 询问除去某个值后的次大值。

代码实现需要注意的地方：

• 要开 long long。

参考代码：

参考代码中变量名与题解中均一致，详见注释。

#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;
//--------------------//
const int N=1e5+1,M=2e6+1;

int n;
//--------------------//
//Graph
struct Edge
{
    int to,nex;
}edge[M];
int tot,head[N];
void add(int from,int to)
{
    edge[++tot].to=to;
    edge[tot].nex=head[from];
    head[from]=tot;
    return;
}
struct Mx//维护最大、次大、次次大的数据结构
{
    LL mx1,mx2,mx3;
    void clear()
    {
        mx1=mx2=mx3=0;
        return;
    }
    void change(LL val)//更新
    {
        if(!mx1||mx1<val)
            mx3=mx2,mx2=mx1,mx1=val;
        else if(!mx2||mx2<val)
            mx3=mx2,mx2=val;
        else if(!mx3||mx3<val)
            mx3=val;
        return;
    }
    LL query1(LL val)//去除某值的最大值
    {
        if(val==mx1)
            return mx2;
        return mx1;
    }
    LL query2(LL val)//去除某值的次大值
    {
        if(val==mx1||val==mx2)
            return mx3;
        return mx2;
    }
};
struct Poi
{
    LL fa;
    Mx dmx,d;
    LL umx;
    LL dia;
}p[N];
//--------------------//
void DFS1(int now,int fa)
{
    p[now].fa=fa;
    for(int to,i=head[now];i;i=edge[i].nex)
    {
        to=edge[i].to;
        if(to==fa)
            continue;
        DFS1(to,now);
        p[now].dmx.change(p[to].dmx.mx1+1);//从当前点出发的链
        p[now].d.change(max(p[to].d.mx1,p[to].dmx.mx1+p[to].dmx.mx2));//不经过当前点的子树内直径
    }
    return;
}
LL ans;
void DFS2(int now)
{
    int fa=p[now].fa;
    if(now!=1)
    {
        p[now].umx=max(p[fa].umx,p[fa].dmx.query1(p[now].dmx.mx1+1))+1;//向子树外延伸的最长链。
        p[now].dia=max(p[fa].dia,p[fa].dmx.query1(p[now].dmx.mx1+1)+max(p[fa].dmx.query2(p[now].dmx.mx1+1),p[fa].umx));//从父节点出发的链拼接而成的长链
        p[now].dia=max(p[now].dia,p[fa].d.query1(max(p[now].d.mx1,p[now].dmx.mx1+p[now].dmx.mx2)));//不经过父节点，不经过当前子树，父节点子树内直径
        //为了方便阅读，分了两步更新子树外直径
    }
    ans=max(ans,p[now].dia*max(p[now].d.mx1,p[now].dmx.mx1+p[now].dmx.mx2));//更新答案
    for(int to,i=head[now];i;i=edge[i].nex)
    {
        to=edge[i].to;
        if(to==p[now].fa)
            continue;
        DFS2(to);
    }
}
//--------------------//
int main()
{
    scanf("%d",&n);
    for(int from,to,i=1;i<n;i++)
        scanf("%d%d",&from,&to),add(from,to),add(to,from);
    DFS1(1,0);
    DFS2(1);
    printf("%lld",ans);
    return 0;
}