接引春雷焚身骨，化灰以养万类荣。

树形背包（模版）
#include<iostream>
#include<vector>
using namespace std;
struct Thing//¶¨ÒåÒ»¸öÎïÆ·½á¹¹Ìå°üÀ¨ÎïÆ·ÊôÐÔÌå»ýºÍ¼ÛÖµ 
{
	int vi;
	int wi;
};
/*¶¨ÒåÒÔÏÂÈ«¾Ö±äÁ¿*/ 
vector< vector<int> >tree;//¶¨ÒåÒ»¸ö¶þάÊý×é´æ´¢¸÷¸ö½ÚµãµÄ×Ó½ÚµãÐÅÏ¢ 
vector<Thing>things; //¶¨ÒåÎïÆ·Êý×é´æ´¢ÎïÆ·µÄÐÅÏ¢ 
int N,V;//¶¨ÒåÎïÆ·µÄÊýÁ¿ºÍ±³°üµÄÌå»ý 
int ans[110][110]; //¶¨Òå¶þάÊý×é´æ´¢´ð°¸ans[i][j]±íʾÔÚÑ¡½ÚµãiÇÒÌå»ý²»³¬¹ýjµÄÇ°ÌáÏÂËùÄܵõ½µÄ×î´ó¼ÛÖµ 
void dfs(int Node)
{/*´Ëº¯ÊýµÄ¹¦ÄÜÊÇÔڵõ½Ò»¸ö½ÚµãºóÎÒÃÇÒª°ÑÔÚÑ¡Õâ¸ö½ÚµãµÄÇé¿öÏÂ
   µÄÿһÌå»ýϵÄ×î´óÖµ¶¼Çó³öÀ´²¢´æÈëansÊý×éÖÐ */
	if(things[Node].vi <= V)//ÏÈÅжϱ³°üÄÜ·ñ·Åϸýڵã´ú±íµÄÎïÆ·Èç¹û¿ÉÒÔÔò½øÈëÅÐ¶Ï 
	{
		if(tree[Node].size()==0||things[Node].vi == V)
    	{/*ÅжÏÈç¹û¸Ã½ÚµãûÓÐ×Ó½Úµã»òÆä´ú±íµÄÎïÆ·Ìå»ýÇ¡ºÃµÈÓÚ±³°üÌå»ý
		   ÔÚÕâÁ½ÖÖÇé¿ö϶¼²»±ØÔÙÈ¥¿¼ÂǸýڵãµÄ×Ó½ÚµãÔõôѡÔñÖ±½Ó¸³Öµ*/ 
    		for(int i=things[Node].vi;i<=V;i++)
    		{/*½«´óÓÚ»òµÈÓÚ¸ÃÎïÆ·µÄ¸÷¸öÌå»ýÈ«¸³Îª¸ÃÎïÆ·µÄ¼ÛÖµ
			   ²¢½«ÆäËûÌå»ýÈ«¸³ÖµÎª0ÕâÀïÒòΪansΪȫ¾Ö±äÁ¿ËùÒÔ
			   ¸÷µã±¾Éí¾ÍÒÔ¸³³õֵΪ0ÔÚÕâÀï¾Í²»ÔÙ½øÐÐÕâÒ»²Ù×÷*/
    			ans[Node][i]=things[Node].wi;
    		}	
    	}
    	else//·ñÔòÎÒÃÇÐèÒª¿¼ÂÇÆä×Ó½ÚµãµÄÑ¡ÔñÇé¿ö 
    	{
    		for(int k=0;k<tree[Node].size();k++)//ÎÒÃÇÒª±éÀú¸÷¸ö×Ó½Úµã 
    		{
				dfs(tree[Node][k]);//Ê×ÏÈÎÒÃÇÇó³öÑ¡Õâ¸ö×Ó½ÚµãµÄÇé¿öϸ÷Ìå»ýϵÄ×îÓŽâ 
    			for(int i=V-things[Node].vi;i>=0;i--)
    			{/*ÎÒÃÇ¿ªÊ¼ÇóÑ¡µ±Ç°½ÚµãµÄÇé¿öϸ÷Ìå»ýϵÄ×îÓŽâ
				   ÎÒÃǵÄÌå»ý´ÓV-things[Node].vi¿ªÊ¼µ½0ÒòΪÎÒÃÇ
				   È·¶¨ÁËÑ¡µ±Ç°ÎïÆ·ËùÒÔҪΪËûÁô³ö¿Õ¼ä£¬Ìå»ý´Ó´ó
				   µ½Ð¡ÊÇÒòΪºÍ01±³°üÒ»Ñù×Ó½ÚµãµÄÿÖÖÌå»ýÖÁ¶à¿ÉÒÔÑ¡Ò»±é*/
    				for(int j=0;j<=i;j++)//µ±Ç°0µ½iÕâ¸ö·¶Î§¾ÍÊÇÕâ¸ö×Ó½ÚµãÒÔÏÂËùÄÜÕ¼ÓõÄÌå»ýÎÒÃÇÒª´ÓÕâЩÌå»ýÖÐÑ¡³ö×îÓŵÄÄǸöÌå»ý 
    					ans[Node][i] = max(ans[Node][i],ans[Node][i-j]+ans[tree[Node][k]][j]);
						/*״̬תÒÆÎÒÃÇÒªÓÃÔÚ²»Ñ¡¡¢ÒÔ¼°·Ö±ð´ÓÕâ¸ö×Ó½ÚµãÒÔÏÂÑ¡×ÜÌå»ýΪ1¡¢2¡­¡­iµÄÎïÆ·ÖÐ
						  Ñ¡ÔñÒ»¸ö×î¼Ñ¾ö²ß£¬¼´±È½Ïµ±Ç°¼ÛÖµºÍÑ¡²»Í¬Ìå»ýϵļÛÖµ·Ö±ð×÷±È½Ï*/
    			}
    		}
    		for(int i=V;i>=things[Node].vi;i--)//×îºóÎÒÃÇÒª½«ÎÒÃǵĸù½ÚµãµÄ¼ÛÖµ¼ÓÈë¼´¿ªÊ¼ÎÒÃÇΪ֮¿Õ³öµÄÌå»ý 
    		{//ÔÚÕâ¸öÌå»ýÒÔÉϵÄÈ«²¿¼ÓÉÏÕâ¸ö½Úµã´ú±íµÄÎïÆ·µÄ¼ÛÖµ 
    			ans[Node][i] = ans[Node][i-things[Node].vi] + things[Node].wi;
    		}
    		for(int i = 0;i < things[Node].vi;i++ )
			{/*Õâ¸öÌå»ýÒÔϵĴú±íÕâ¸ö½Úµã²»ÄÜÑ¡Õâ¸ö½Úµã²»ÄÜÑ¡ÄÇôËûËùÓеÄ×Ó½ÚµãÒ²²»ÄÜÑ¡ËùÒÔÈ«²¿¸³³õֵΪ0
			   ÕâÀïÐèÒª¸³ÖµÊÇÒòΪÎÒÃÇÔÚÉÏÃæµÄÇó´óÌå»ý×îÓŽâµÄʱºòÓõ½ÁËÕâ¿éÌå»ýÎÒÃÇÒѾ­ÎªËûÃǸ³ÉÏÖµÁË
			   ËüÃÇÒѾ­²»ÊÇ0ÁËËùÒÔÕâÀïµÄ¸³0²»ÄÜÊ¡*/
				ans[Node][i]=0;
			}
    	}
	}
}
int main()
{
	int root;      //¶¨ÒåÒ»¸ö±äÁ¿Ò»»á´¢´æ¸ù½Úµã 
	cin>>N>>V;     //ÊäÈëÎïÆ·ÊýºÍ±³°üÌå»ý 
	tree.resize(N);//¿ª±Ù¿Õ¼äÒ»¸öÊý×é´¢´æ¸÷½ÚµãµÄ×Ó½ÚµãÐÅÏ¢´Ó¶ø´¢´æÕû¿ÃÊ÷µÄ½áµã¹Øϵ 
	for(int i=0;i<N;i++)//±éÀúÊäÈëÎïÆ·ÐÅÏ¢ 
	{
		int v,w,f;
		cin>>v>>w>>f;
		things.push_back({v,w});//½«ÎïÆ·ÐÅÏ¢·ÅÈëÎïÆ·Êý×éthings 
		if(f==-1)//¼ì²é¸Ã½ÚµãµÄ¸¸½ÚµãÊÇÄÄÒ»¸öÈç¹ûËüÊǸ¸½ÚµãÔò¼Ç¼Ëü 
		{
			root=i;
		}
		else//Èç¹û²»ÊǸ¸½ÚµãÔÚÔÚÆ丸½Úµã´ú±íµÄһάÊý×éÖдæÈë¸Ã½Úµã 
		{
			tree[f-1].push_back(i);//ÎÒÃǵĽڵãϱê´Ó0µ½n-1ÊäÈëµÄ¸¸½ÚµãÊÇ1µ½nËùÒÔÈÃÊäÈëµÄf¼õÈ¥1¼´ÎÒÃÇÒªÕҵĸ¸½Úµã 
		}
	}
	dfs(root);//´Ó¸ù½Úµãµ÷Óõݹ麯Êý 
	cout<<ans[root][V]<<endl;//Êä³ö×îÖÕ½á¹û 
	return 0;
} 

//https://zhuanlan.zhihu.com/p/648341058


迪杰斯特拉算法
void dijkstra() {
	vector<long long>dis(N,1e18);
	vector<bool>st(N,0);
	dis[1]=0;
	for(;;) {
		int u=-1;
		for(int j=1; j<=n; j++)
			if(!st[j]&&(u==-1||dis[u]>dis[j]))u=j;
		if(u==-1)break;
		st[u]=1;
		for(int j=1; j<=n; j++) {
			int v=j,w=G[u][j];
			dis[v]=min(dis[v],dis[u]+w);
		}
	}
	printf("%lld\n",dis[t]);
}
bellman_ford算法
void bf(){
	vector<long long>dis(N,1e18);
	dis[1]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int u=G[j].u,v=G[j].v,w=G[j].w;
			dis[v]=min(dis[v],dis[u]+w);
		}
	} 
	for(int i=2;i<=n;i++)printf("%lld\n",dis[i]);
} 
SPFA算法
void SPFA(){
	vector<long long>dis(N,1e18);
	vector<bool>st(N,0);
	queue<int>q;
	q.push(1),dis[1]=0,st[1]=1;
	while(q.size()){
		int u=q.front();q.pop(),st[u]=0;
		for(auto it:G[u]){
			int v=it.first,w=it.second;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!st[v])q.push(v),st[v]=1;
			}
		}
	}
	for(int i=2;i<=n;i++)printf("%lld\n",dis[i]);
}
		// 判空
并查集
==0	:
void init(int n) {//初始化 自己的父亲是自己 
	for(int i=1; i<=n; i++)p[i]=i;
}
int find(int u) {// 查询u的祖先 
	return u==p[u] ? u: p[u]=find(p[u]);
}
void merge(int u,int v){//合并x，y 
	int x=find(u),y=find(v);
	p[x]=y;
}
#质数判断：
bool zs(int n){

for(int i=2;i<=n/i;i++)if(n%i==0)return 0;return n>1;}

/* int st[N], hh; // 数组模拟栈 st[++hh] = x; // 入栈 hh--; // 出栈 st[hh] // 栈顶 hh C++参考手册：https://www.shouce.ren/api/c/ */ int que[N], hh, tt=-1;que[++tt] = x; // 入队++hh; // 出队que[hh] // 队首que[tt] // 队尾tt - hh == -1 // 判空stack st;queue que;

vector代码调用 push_back(x)---放入到最后 pop_back()---拿出最后一个 size()---元素数量 empty()---判断是否为空

欧拉筛法（质数筛）void get pri(int n){tt[0]=0;tt[1]=1;for(int i=2;i<=n;i++){if(!tt[i])pri[++pn]=i;for(int j=1;pri[j]<=n/i;j++){tt[ipri[j]]=1;if(ipri[j]==0)break;}}} 二叉树之知前中序求后序：#include<bits/stdc++.h>using namespace std;void dfs(string a,string b) {if(a.size()==0)return;char rt=a[0];int k=b.find(rt);dfs(a.substr(1,k),b.substr(0,k));dfs(a.substr(k+1),b.substr(k+1));cout<<rt;}int main() {string a,b,c;cin>>a>>b;dfs(a,b);return 0;}

名字竞技场http://namerena.github.io/

二叉树之知中后序求前序：
#include<bits/stdc++.h>
using namespace std;
void dfs(string b,string c) {
if(b.size()==0)return;
char rt=c.back();
int k=b.find(rt);
cout<<rt;
dfs(b.substr(0,k),c.substr(0,k));
dfs(b.substr(k+1),c.substr(k,c.size()-k-1));
}
int main() {
string b,c;
cin>>b>>c;
dfs(b,c);
return 0;
}
区间最大值维护代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,l,r,a[N],f[N][22];
//f[i][j] 表示维护区间[i,i+2^j-1]最大值
//f[i][0] =a[i]
//f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1])
void ST(){
for(int i=1;i<=n;i++)f[i][0]=a[i];
for(int j=1;j<=20;j++)
for(int i=1;i+(1<<j)-1<=n;i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
int query(int l,int r){
int k=log2(r-l+1);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
ST();
while(m--){
scanf("%d%d",&l,&r);
printf("%d\n",query(l,r));
}
return 0;
}//寻找根节点	
int rt=1;
for(int i=1;i<=n;i++){
if(!st[i]){
rt=i;break;
}
}
//
priority_queue<int>q;//默认大顶堆
//priority_queue<int,vector<int>,less<int>>q大顶堆，容器vector，比较函数less
//priority_queue<int,vector<int>,greater<int>>q小顶堆，容器vector，比较函数greater
//push();入堆
//pop();出堆
//top();堆顶
//size();元素数量
//双指针问题模板
for(int i=1,j=1;i<=n;i++){
while(j<=m&&xxx)j++;
}
归并排序
//void ms(int l（1）,int r（n）){
//	if(l>=r) return;
//	int mid=(l+r)/2,i=l,j=mid+1,p=0;
//	ms(l,mid);
//	ms(mid+1,r);
//	while(i<=mid&&j<=r){
//		if(a[i]<=a[j]){
//			t[++p]=a[i++];
//		}else{
//			t[++p]=a[j++];
//		}
//	}
//	while(i<=mid) t[++p]=a[i++];
//	while(j<=r) t[++p]=a[j++];
//	for(int i=1;i<=p;i++) a[l++]=t[i];
//}
死人老登儿，凸(艹皿艹 )
线段树求区间和
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N=1e6+10;
int n,q;
long long sum[N<<2];
void Pushup(int rt){
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){
	if(l==r){
		scanf("%lld",&sum[rt]);
		return;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	Pushup(rt);
}
void update(int L,int R,int v,int l,int r,int rt){//更新 
	if(l==r){
		sum[rt]+=v;
		return;
	}
	int m=(l+r)>>1;
	if(L<=m) update(L,R,v,lson);
	if(m<R) update(L,R,v,rson);
	Pushup(rt);
}
long long query(int L,int R,int l,int r,int rt){//查询 
	if(L<=l&&r<=R){
		return sum[rt];
	}
	int m=(l+r)>>1;
	long long res=0;
	if(L<=m) res+=query(L,R,lson);
	if(m<R) res+=query(L,R,rson);
	return res;
}
int main(){
	scanf("%d%d",&n,&q);
	build(1,n,1);
	int op,a,b;
	while(q--){
		scanf("%d%d%d",&op,&a,&b);
		if(op==1){
			update(a,a,b,1,n,1);
		}else{
			printf("%lld\n",query(a,b,1,n,1));
		}
	}
	return 0;
}
```
#include<bits/stdc++.h>
using namespace std;

int n,m;
int head[50010],cnt;

struct node{
	int v,nxt;
}e[50010]; 

void add(int a,int b){
	cnt++;
	e[cnt].v=b;
	e[cnt].nxt=head[a];
	head[a]=cnt;
}
int w[50010],val[50010],d[50010],dp[10001][10001];
void dfs(int u){
	if(head[u]==0||w[u]==m){
		for(int i=w[u];i<=m;i++){
			dp[u][i]=val[u];
		}
	}else{
		for(int k=head[u];k;k=e[k].nxt){
			int v=e[k].v;
			dfs(v);
			for(int i=m-w[u];i>=0;i--)
				for(int j=0;j<=i;j++){
					dp[u][i]=max(dp[u][i],dp[v][j]+dp[u][i-j]);
				}
		}
		for(int i=m;i>=w[u];i--){
			dp[u][i]=dp[u][i-w[u]]+val[u];
		}
		for(int i=w[u]-1;i>=0;i--){
			dp[u][i]=0;
		}
	}
}
int main(){
	cin>>n>>m;
    
    memset(dp,0,sizeof(dp));
    
	for(int i=1;i<=n;i++){
		cin>>d[i];
		add(d[i],i);
	}
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n;i++) cin>>val[i];
	
	dfs(0);
	cout<<dp[0][m];
	return 0;
}

#include<bits/stdc++.h>
using namespace  std;
const int N=25100;
struct node{
	int v,nxt,w;
}e[62100];
int cnt,head[N];
void add(int a,int b,int c){
	cnt++;
	e[cnt].v=b;
	e[cnt].nxt=head[a];
	e[cnt].w=c;
	head[a]=cnt;
}
int n,m,s,t,a,b,c,dij[N],vis[N],fom[N];
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	queue<int>q;
	memset(dij,127,sizeof(dij));
	dij[s]=0;
	q.push(s);
	vis[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(dij[u]+e[i].w<dij[v]){
				dij[v]=dij[u]+e[i].w;
				if(!vis[v])q.push(v);
			}
		}
	}
	cout<<dij[t];
	return 0;
}
```