本文共 1434 字,大约阅读时间需要 4 分钟。
树形DP的问题就是在一棵树上DP,要做这类题目
1、建树
2、写状态转移方程(树形DP的重点)
3、dfs(),分为两种,一种是从根一直找到子节点,然后子节点不断把值更新到父节点中,另一种是父节点将自己的值不断的更新给子节点,也就是说一种是自上而下,一种是自下而上,
一、建树
建树可以有两种方式
例如现在要建这么一棵树,1是根节点,孩子是23,2的孩子是45,
按边来说就是1 2,1 3,2 4,2 5四条边组成的树
1
2 3
4 5
1、用邻接链表的方式,代码见
第一维 第二维
1 2,3
2 1,4
3 1
4 2
5 2
#include<algorithm>
using namespace std;
#include<vector>
vector<int> adj[N];
for(int i=0;i<4;i++)
{
scanf("%d%d",&a,&b);
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs里边找a的子节点可以这么写
for(int i=0;i<adj[a].size();i++)
{
int v=adj[a][i];//v即a的一个子节点
}
2、建树的方式,代码见
int next[N];//next[e]表示的是
int head[N];
int v[N];
int w[N];
int e=1;
add(int a,int b,int c)
{
v[e]=b;//第e条边的邻结点是b,即第e条边是这样的:a-------------b,中间--------表示这是第e条边,e表示a在第e条边
w[e]=c;//第e条边的权值是c
next[e]=head[a];//next[e]存的是a之前还在哪条边中,因为head[a]就表示a在的边
head[a]=e++;//head[a]表示a在的边是e++;
}
//dfs()中遍历子节点
for(int i=head[u];i!=-1;i=next[i])
{
v[i]就是u的子节点
}
for(int i=0;i<4;i++)
{
scanf("%d%d%d",&a,&b,&c);//a,b是边的两个端点,c是边的权值
add(a,b);
add(a,b,c);
}
经过这个过程建的树,这么理解建无向树,边有8条12,21,13,31,24,42,25,52;
e v[e] next[e] head[a]
1 2 head[1]=-1; head[1]=1
2 1 head[2]=-1; head[2]=2
3 3 head[1]=1; head[1]=3
4 1 head[3]=-1; head[3]=4
5 4 head[2]=2; head[2]=5;
6 2 head[4]=-1; head[4]=6;
7 5 head[2]=5; head[2]=7;
8 2 head[5]=-1; head[5]=8;
我们从根节点1开始找,1所在的边是head[1]=3;第三条边的邻结点是v[3]=3;
我们在通过3为根找他的子节点,dfs(3),递归到子节点,对于1来说可以再找他的其他孩子,我们通过next[i]找,我们已经知道1在的边i是head[1]=3,即i=3,要想找1的其他孩子,即找1还在哪条边上next[i]=1,说明1还在第一条边上,通过v[1]=2,我们又可以找到1的另一子节点
转载地址:http://jrddi.baihongyu.com/