首页 > 试题广场 >

树上三角链

[编程题]树上三角链
  • 热度指数：139 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一棵包含个节点且以节点为根节点的树。
你需要从中选出个不同的节点，使得其两两之间的最短距离之和最大，并求出这个最大和。
定义树上两点之间的最短距离为这两点之间的简单路径所经过的边的数量。

输入描述:
第一行输入一个正整数。
第二行输入个正整数。节点为节点的父节点。


输出描述:
输出一个整数代表最大和。
示例1

输入

5
4 1 1 4

输出

8

说明

3个节点为3，2，5
节点3与2的最短距离为3
节点3与5的最短距离为3
节点2与5的最短距离为2
3+3+2=8
算法知识视频讲解
添加回答
adgjl头像 adgjl
两两之间的最短距离为节点到交点距离的两倍。
使用递归解决，在遍历过程中：
当前节点不是交点，返回子树中的两两之间的最短距离之和最大的三个点；
当前节点为两个节点的交点，返回深度最深的两颗子树的深度以及两颗子树下最长的第三边
当前节点为三个点的共同交点，返回深度最深的三颗子树的深度。
分别计算出每个节点的三种情况的目标值，并选出其中最大的。 

import java.util.*;

public class Main {
    static Node[] tree;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        tree = new Node[n];
        for (int i = 0; i < n; i++) {
            tree[i] = new Node();
        }
        for (int i = 1; i < n; i++) {
            int parent = scanner.nextInt();
            tree[parent-1].addChild(tree[i]);
        }
        int[] max3 = calMaxLength(tree[0]);
        int sumOfMax3 = 0;
        for (int i = 0; i < 3;i++){
            sumOfMax3 += max3[i];
        }
        System.out.println(sumOfMax3*2);
    }
    public static int[] calMaxLength(Node root){
        int maxLsum = 0;
        int maxdeep = 0;
        int[] ret = new int[4];
        int[] c2MaxSum1 = new int[4];
        int[] c3MaxSum = new int[4];
        if(root.child.isEmpty() == false){
            for (Node chi: root.child){
                int[] temp = calMaxLength(chi);
                if(maxdeep < temp[3]){
                    maxdeep = temp[3];
                }
                int c3minidex = -1;//该节点为三个节点的共同交点，计算并与已有最大值比较
                for(int i = 0;i < 3;i++) {
                    if(c3minidex == -1 || c3MaxSum[i] < c3MaxSum[c3minidex] ){
                        c3minidex = i;
                    }
                }
                if(c3MaxSum[c3minidex] < temp[3]) {
                    c3MaxSum[c3minidex] = temp[3];
                    int c3temp = 0;
                    for(int i = 0;i < 3;i++){
                        c3temp += c3MaxSum[i];
                    }
                    if(c3temp > maxLsum){
                        maxLsum = c3temp;
                        ret = c3MaxSum;
                    }
                }
                int c1temp = 0;//该节点不是共同交点，计算并与已有最大值比较
                for (int i = 0;i < 3;i++){
                    c1temp += temp[i];
                }
                if(maxLsum < c1temp){
                    maxLsum = c1temp;
                    ret = temp;
                }
                int[] templ = Arrays.copyOf(temp,3);//该节点为两个节点的共同交点，计算并与已有最大值比较
                Arrays.sort(templ);
                int[] templmax = Arrays.copyOf(c2MaxSum1,3);
                Arrays.sort(templmax);
                int maxoftwo = templ[1] > templmax[1] ? templ[1] : templmax[1];
                if(temp[3] + c2MaxSum1[3] + maxoftwo > maxLsum){
                    maxLsum = temp[3] + c2MaxSum1[3] + maxoftwo;
                    ret = new int[4];
                    ret[0] = temp[3];
                    ret[1] = c2MaxSum1[3];
                    ret[2] = maxoftwo;
                }
                if(c2MaxSum1[3] < temp[3] || (c2MaxSum1[3] == temp[3] && templ[1] > templmax[1])){
                    c2MaxSum1 = temp;
                }
            }
        }
        ret[3] = maxdeep+1;
        return ret;
    }
}
class Node{
    List<Node> child = new ArrayList<>();
    public void addChild(Node child){
        this.child.add(child);
    }
}


编辑于 2021-05-19 01:05:41 回复(0)
寒冰-侠客头像 寒冰-侠客
虽然AC但感觉方法并不太对，非常繁琐，难道正解是树形DP？
推理但并未证明，基础理论是和最大三个点必包含距离最大两个点。
利用“重心”求法先找出距离最大的两个点，再对这两个点分别搜索计算到其他各点距离，求得极值。 
#include<bits/stdc++.h>
using namespace std;
int n,v[100005],dis1[100005],dis2[100005],mlen,mr,m1,m2,ans=0;
vector<int>e[100005];
int dfs(int r,int f)
{
    int i,ans=0,s1=0,s2=0,r1=0,r2=0;
    for(i=0; i<e[r].size(); i++)
    {
        if(f==e[r][i])
            continue;
        int len=dfs(e[r][i],r);
        ans=max(ans,len);
        if(len>s1)
            s2=s1,r2=r1,s1=len,r1=e[r][i];
        else if(len>s2)
            s2=len,r2=e[r][i];
    }
    if(s1+s2>mlen)
    { /**< 记录下最大距离，最大距离时的树根和两个子节点 */
        mlen=s1+s2;
        mr=r,m1=r1,m2 = s2==0?r:r2;
    }
    return ans+1;
}
int getD(int child,int f)
{ /**< bfs出父节点f，子节点child的最深层节点 */
    memset(v,0,sizeof v);
    v[f]=v[child]=1;
    queue<int>q;
    q.push(child);
    int i,t;
    while(q.size())
    {
        t=q.front();
        q.pop();
        for(i=0;i<e[t].size();i++)
            if(v[e[t][i]]==0)
            v[e[t][i]]=1,q.push(e[t][i]);
    }
    return t;
}
void dfs1(int x,int f,int dis[])
{
    for(int i=0; i<e[x].size(); i++)
    {
        if(e[x][i]==f)
            continue;
        dis[e[x][i]]=dis[x]+1;
        dfs1(e[x][i],x,dis);
    }
}
int main()
{
    int i,j,x;
    cin>>n;
    for(i=2; i<=n; i++)
    {
        cin>>x;
        e[x].push_back(i),e[i].push_back(x);
    }
    dfs(1,0);/**< 先找出距离最大两点距离 */
    m1=getD(m1,mr);/**< 用根和两个子节点求出两个距离最远的点m1和m2 */
    if(mr!=m2)
        m2=getD(m2,mr);
    dfs1(m1,0,dis1);/**< m1搜索求出到其他所有点距离 */
    dfs1(m2,0,dis2);/**< m2搜索求出到其他所有点距离 */
    dis1[m2]=0,dis2[m1]=0;
    for(i=1;i<=n;i++)/**< 到第三个点距离和极值 */
        ans=max(ans,dis1[i]+dis2[i]);
    cout<<ans+mlen;
    return 0;
}


发表于 2021-05-14 15:41:43 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 腾讯音乐娱乐集团 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
2条回答 4012浏览

热门推荐

通过挑战的用户

相关试题

树上三角链

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号