首页 > 代码库 > 树形DP经典题

树形DP经典题

2024-07-06 13:36:14   230人阅读

题目传送门

题意：

给出一棵树，求离每个节点最远的点的距离

思路：

把无根树转化成有根树分析，

对于上面那棵树，要求距结点2的最长距离，那么，就需要知道以2为顶点的子树（蓝色圈起的部分，我们叫它Tree（2）），距顶点2的最远距离L1

还有知道2的父节点1为根节点的树Tree（1）-Tree(2)部分（即红色圈起部分），距离结点1的最长距离+dist(1,2) = L2，那么最终距离结点2最远的距离就是max{L1，L2}


f[i][0],表示顶点为i的子树的，距顶点i的最长距离
f[i][1],表示Tree(i的父节点)-Tree(i)的最长距离+i跟i的父节点距离


要求所有的f[i][0]很简单，只要先做一次dfs求每个结点到叶子结点的最长距离即可。
然后要求f[i][1], 可以从父节点递推到子节点，

假设节点u有n个子节点，分别是v1,v2...vn
那么
如果vi不是u最长距离经过的节点，f[vi][1] = dist(vi,u)+max(f[u][0], f[u][1])
如果vi是u最长距离经过的节点，那么不能选择f[u][0],因为这保存的就是最长距离，要选择Tree（u）第二大距离secondDist,
可得f[vi][1] = dist(vi, u) + max(secondDist, f[u][1])

贴一段自己AC的代码：
<pre name="code" class="cpp">//求树的最长路径问题
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 10100
struct node
{
    int id;
    int next;
    int len;
};

struct node edge[MAXN*2];
int head[MAXN];  //用来表示头节点
int d[MAXN][2];  //用来表示状态集
int smaxn[MAXN];//次大距离
int smaxnid[MAXN]; //次最大值所经过的子节点
int maxnid[MAXN];  //最大值所经过的子节点
int ptr;

void init()
{
    ptr=0;
    memset(head,-1,sizeof(head));
}

void addEdge(int a,int b,int len)  //树形DP模版和上一篇一样的
{
    edge[ptr].id=b;
    edge[ptr].next=head[a];
    edge[ptr].len=len;
    head[a]=ptr++;
    edge[ptr].id=a;
    edge[ptr].next=head[b];
    edge[ptr].len=len;
    head[b]=ptr++;
}
//求所有节点的d[v][0],同时记录最大距离和第二大距离从哪个子节点过来，p是U的父节点，该函数用来求u节点到叶子节点
void fds1(int u,int p)
{
    d[u][0]=0;
    smaxn[u]=0;
    int i;
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].id;
        if(v==p)    continue;
        fds1(v,u);
        if(smaxn[u]<d[v][0]+edge[i].len)
        {
            smaxn[u]=d[v][0]+edge[i].len;
            smaxnid[u]=v;
            if(smaxn[u]>d[u][0])
            {
                swap(smaxn[u],d[u][0]);
                swap(smaxnid[u],maxnid[u]);
            }
        }
    }
}
//求所有节点的d[v][1]，u为v的父节点，p为u的父节点
void fds2(int u,int p)
{
    int i;
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].id;
        if(v==p)
            continue ;
        if(v!=maxnid[u])
            d[v][1]=edge[i].len+max(d[u][0],d[u][1]);
        else
            d[v][1]=edge[i].len+max(smaxn[u],d[u][1]);
        fds2(v,u);
    }

}
int main()
{
    //freopen("a.txt","r",stdin);
    int n,i,v,len;
    while(scanf("%d",&n)!=EOF)
    {
        init();
        for(i=2;i<=n;i++)
        {
            scanf("%d%d",&v,&len);
            addEdge(i,v,len);
        }
        fds1(1,-1);
        fds2(1,-1);
        for(i=1;i<=n;i++)
            printf("%d\n",max(d[i][0],d[i][1]));
    }

}





































        

            
                
                  
                
                

                    联系

                    我们