Liveddd's Blog

愛にできることはまだあるかい

SP6717 TWOPATHS - Two Paths

发表于 更新于 分类于
本文字数： 3.3k 阅读时长 ≈ 7 分钟

比较裸的换根 DP。

虚高题。

update on 2022.11.13。原题解被 @zhanghenglei 所 Hack。现在已将解法修正，如果仍有问题，欢迎指出qwq。

不难想到用 $f_x,g_x$ 分别表示以 $x$ 为根的子树内和子树外最长链的长度。答案就是 $\max{f_x\times g_x}$。$f_x$ 很容易求，考虑 $g_x$ 怎么求。

$g_x$ 可以从父亲节点转移过来，这启发我们可以类似于换根 DP 的方法来求 $g_x$。

考虑怎么构成一条子树外的链。无非是从父节点往上延伸，或者从父节点往下延伸的链。再将他们最长的两段在父节点拼起来成为一个答案。

但是我们选取的两段链不能在 $x$ 的子树中。这就意味着我们需要先求出，从父节点往下延伸的链的最大值、亚大值和次大值，以及对应的子节点。转移时判断一下所选的链有没有在 $x$ 的子树中就行。

从该节点 $x$ 往上延伸的最长链也可以通过最大值和亚大值通过换根 DP 来求出，也比较简单。

但是这样解是有漏洞的，$g_x$ 求出来只是恰好经过其父节点的最长链，而不是整棵树中除去该子树的最长链，就像这样：

output : 30
answer : 36

所以我们需要再多记一个 $h_x$ 表示该节点的父节点的子树之外的最长链，转移与上面类似。

具体可看看代码，有一些注释。有点繁琐，但还是比较好写。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}

int n;
ll ans;
int tot,head[N],ver[N<<1],ne[N<<1];
int d[N][3],l[N],t[N][3],f[N],g[N],h[N];
int res;
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
void dfs1(int x,int fa)
{
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs1(y,x);
        if(d[y][0]+1>=d[x][0])
        {
            d[x][2]=d[x][1],t[x][2]=t[x][1];
            d[x][1]=d[x][0],t[x][1]=t[x][0];
            d[x][0]=d[y][0]+1,t[x][0]=y;
        }
        else if(d[y][0]+1>=d[x][1])
        {
            d[x][2]=d[x][1],t[x][2]=t[x][1];
            d[x][1]=d[y][0]+1,t[x][1]=y;
        }
        else if(d[y][0]+1>=d[x][2])
            d[x][2]=d[y][0]+1,t[x][2]=y;
        //处理出从该节点往下延伸的链的最大值、亚大值和次大值
        //以及其所对应的儿子
        f[x]=max(f[x],f[y]);//从子节点转移
    }
    f[x]=max(f[x],d[x][0]+d[x][1]);//从自己转移
}
void dfs2(int x,int fa)
{
    ans=max(ans,1ll*f[x]*max(g[x],h[x]));//统计答案
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        l[y]=l[x]+1;
        if(t[x][0]&&t[x][0]!=y)
            l[y]=max(l[x],d[x][0])+1;
        else if(t[x][1])
            l[y]=max(l[x],d[x][1])+1;
        //转移从该节点向上延伸的最长链
        int res[4];
        res[0]=t[x][0]!=y?d[x][0]:0;
        res[1]=t[x][1]!=y?d[x][1]:0;
        res[2]=t[x][2]!=y?d[x][2]:0;
        res[3]=l[x];
        sort(res,res+4);
        //从四条链中选取合法的最长的两条
        g[y]=max(g[x],res[2]+res[3]);
        h[y]=h[x];
        dfs2(y,x);
        res[0]=t[y][0]!=y?d[y][0]:0;
        res[1]=t[y][1]!=y?d[y][1]:0;
        res[2]=t[y][2]!=y?d[y][2]:0;
        sort(res,res+3);
        h[x]=max(h[x],res[1]+res[2]);
        //转移该节点的父节点的子树之外的最长链
    }        
}
int main()
{
    read(n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u,v);
        add(u,v);
        add(v,u);
    }
    dfs1(1,0);
    dfs2(1,0);
    printf("%lld\n",ans);
    return 0;
}