树形DP
链式前向星
一种把多个链表（数组模拟）的元素存在一个数组里的数据结构
结构
const int MAXN=(int)1e5+10;
const int MAXM=(int)5e5+10;
int head[MAXN];
struct Edge{
int to,w,next;
} edge[MAXM];
int cnt;
head[i]表示以i为起点的边所在链表的第一条边的编号
edge[i]表示编号为i的边，to是边的终点，w是边的权值，next表示这条链表的下一条边的编号
cnt表示当前边的数量
添边
void add(int u,int v,int w)
{
edge[++cnt].next=head[u];
edge[cnt].to=v;
edge[cnt].w=w;
head[u]=cnt;
} 无向图一条边需要添加两次
当n为偶数时，x^1=n+1
当n为奇数时，x^1=n-1
利用这个性质可以方便地得到反向的边的存储位置
遍历
for (int i=head[st];i!=0;i=edge[i].next) {}
遍历以st为起点的所有边，如果边以0开始编号，next需要初始化为-1
查看3道真题和解析
投递大连飞创信息技术有限公司等公司10个岗位