树形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