• 树形DP YBTOJ专项

    被自己之前的代码丑哭了:（

    没有上司的舞会&树上求和

    给出一个 n 个结点的树，每个结点都有一个权值 a ，请你选择一些结点，使得被选结点的权值和最大，且被选结点之间不能存在父子关系，即选了父亲不能选儿子，选了儿子不能选父亲。

    1. #include
    2. using namespace std;
    3. #define int long long
    4. const int N=1000010;
    5. int n,tot,f[N][2],ans,head[N],leader[N];
    6. bool vis[N];
    7. struct edge{int to,next;}e[N<<1];
    8. int read()
    9. {
    10.     int x=0,f=1;
    11.     char ch=getchar();
    12.     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    13.     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    14.     return x*f;
    15. }
    16. void add_edge(int u,int v)
    17. {
    18.     e[++tot].to=v;
    19.     e[tot].next=head[u];
    20.     head[u]=tot;
    21. }
    22. void dfs(int u)
    23. {
    24.     vis[u]=1;
    25.     for(int i=head[u];i;i=e[i].next)
    26.     {
    27.         int v=e[i].to;
    28.         if(!vis[v])
    29.         {
    30.             dfs(v);
    31.             f[u][1]+=f[v][0];
    32.             f[u][0]+=max(f[v][0],f[v][1]);
    33.         }
    34.     }
    35. }
    36. signed main()
    37. {
    38.     n=read();
    39.     for(int i=1;i<=n;i++) f[i][1]=read();
    40.     for(int i=1;i
    41.     {
    42.         int v=read();
    43.         int u=read();
    44.         leader[v]=1;
    45.         add_edge(u,v);
    46.     }
    47.     for(int i=1;i<=n;i++)
    48.     {
    49.         if(leader[i]==0)
    50.         {
    51.             dfs(i);
    52.             printf("%lld",max(f[i][0],f[i][1]));
    53.             return 0;
    54.         }
    55.     }
    56.     return 0;
    57. }

    结点覆盖

    给出一棵有根树，要求选出一些结点。若选中某个结点，则它本身、它的父亲结点和儿子结点被覆盖。选出第 i 个结点需要一定的花费 ，求覆盖这棵树所需的最小花费。

    1. #include
    2. using namespace std;
    3. #define int long long
    4. const int N=100010;
    5. int n,a[N],tot,head[N],f[N][3];
    6. struct edge{int to,next;}e[N<<1];
    7. int read()
    8. {
    9.     int x=0,f=1;
    10.     char ch=getchar();
    11.     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    12.     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    13.     return x*f;
    14. }
    15. void add_edge(int u,int v)
    16. {
    17.     e[++tot].to=v;
    18.     e[tot].next=head[u];
    19.     head[u]=tot;
    20. }
    21. void dfs(int u,int fa)
    22. {
    23.     f[u][0]=a[u];
    24.     bool flag=0;
    25.     int res=1e18;
    26.     for(int i=head[u];i;i=e[i].next)
    27.     {
    28.         int v=e[i].to;
    29.         if(fa==v) continue;
    30.         dfs(v,u);
    31.         f[u][0]+=min(f[v][0],min(f[v][1],f[v][2]));
    32.         f[u][2]+=min(f[v][0],f[v][1]);
    33.         if(f[v][0]1]) flag=1;
    34.         else res=min(res,f[v][0]-f[v][1]);
    35.         f[u][1]+=min(f[v][0],f[v][1]);
    36.     }
    37.     if(!flag) f[u][1]+=res;
    38. }
    39. signed main()
    40. {
    41.     n=read();
    42.     for(int i=1;i<=n;i++)
    43.     {
    44.         int u=read();
    45.         a[i]=read();
    46.         int m=read();
    47.         for(int j=1;j<=m;j++)
    48.         {
    49.             int v=read();
    50.             add_edge(u,v);
    51.             add_edge(v,u);
    52.         }
    53.     }
    54.     dfs(1,0);
    55.     printf("%lld",min(f[1][0],f[1][1]));
    56.     return 0;
    57. }

    最长距离

    给出一个以 1 为根的 n 个结点的树，树边有权值，求出每个结点与相距最远结点间的距离 。

    dfs1先只向下找，dfs2去取向下/先向上再向下的最大值，就是要特判一下u是否本身就在父结点的最长子链中。

    1. #include
    2. using namespace std;
    3. #define int long long
    4. struct edge{int to,next,w;}e[10010];
    5. int n,m,ans[10010],head[10010],f[10010][3];
    6. void add_edge(int u,int v,int w)
    7. {
    8. 	e[++m].to=v;
    9. 	e[m].w=w;
    10. 	e[m].next=head[u];
    11. 	head[u]=m;
    12. }
    13. void dfs1(int u)
    14. {
    15. 	int maxx1,maxx2;
    16. 	maxx1=maxx2=0;
    17. 	for(int i=head[u];i;i=e[i].next)
    18. 	{
    19. 		int v=e[i].to;
    20. 		dfs1(v);
    21. 		if(f[v][0]+e[i].w>maxx1)
    22. 		{
    23. 			ans[u]=v;
    24. 			maxx2=maxx1;
    25. 			maxx1=f[v][0]+e[i].w;
    26. 		}
    27. 		else if(f[v][0]+e[i].w>maxx2) maxx2=f[v][0]+e[i].w;
    28. 	}
    29. 	f[u][0]=maxx1;
    30. 	f[u][1]=maxx2;
    31. }
    32. void dfs2(int u)
    33. {
    34. 	for(int i=head[u];i;i=e[i].next)
    35. 	{
    36. 		int v=e[i].to;
    37. 		if(ans[u]==v) f[v][2]=max(f[u][1],f[u][2])+e[i].w;
    38. 		else f[v][2]=max(f[u][0],f[u][2])+e[i].w;
    39. 		dfs2(v);
    40. 	}
    41. }
    42. signed main()
    43. {
    44. 	while(scanf("%d",&n)!=EOF)
    45. 	{
    46. 		memset(head,0,sizeof head);
    47. 		m=f[1][0]=f[1][1]=f[1][2]=0;
    48. 		for(int i=2;i<=n;i++)
    49. 		{
    50. 			int fa,w;
    51. 			scanf("%d%d",&fa,&w);
    52. 			add_edge(fa,i,w);
    53. 			f[i][0]=f[i][1]=f[i][1]=0;
    54. 		}
    55. 		dfs1(1);dfs2(1);
    56. 		for(int i=1;i<=n;i++) printf("%d\n",max(f[i][0],f[i][2]));
    57. 	}
    58. 	return 0;
    59. }

    选课方案

    在大学里，每个学生为了达到一定的学分，必须从很多课程里选择一些课程来学习，有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a ，才能学习课程 b ）。一个学生要从这些课程里选择 m 门课程学习，问他能获得的最大学分是多少？

    有一个点：森林无疑是难搞的，但是可以假设有一个点是所有根节点的父亲，那就好办了许多。 f[i][j] 表示对于节点 i ， 一共选择 j 门课所能得到的最大学分(包括他本身)。选择他的所有子节点的前提是一定要选择这个节点，所 f[i][1] 一定等于 i 节点的权值

    在枚举 j 的时候需要注意：由于 f[u][j] 由 f[u][j - k] 更新得到，那么就需要保证更新的时候 f[u][j - k] 没有被更新，由于 k 是一个正整数，所以我们倒序枚举 j 即可

    1. #include
    2. using namespace std;
    3. int n,m,f[1010][1010],head[100010],cnt;
    4. struct edge{int u,v; }e[100010];
    5. void add(int from,int to)
    6. {
    7. 	e[++cnt].v=head[from];
    8. 	e[cnt].u=to;
    9. 	head[from]=cnt;
    10. }
    11. void dp(int now)
    12. {
    13. 	for(int i=head[now];i;i=e[i].v)
    14. 	{
    15. 		int go=e[i].u;
    16. 		dp(go);
    17. 		for(int j=m+1;j>=1;j--)
    18. 		for(int k=0;k
    19. 		    f[now][j]=max(f[now][j],f[go][k]+f[now][j-k]);
    20. 	}
    21. }
    22. int main()
    23. {
    24. 	scanf("%d%d",&n,&m);
    25. 	for(int i=1;i<=n;i++)
    26. 	{
    27. 		int fa;
    28. 		scanf("%d%d",&fa,&f[i][1]);
    29. 		add(fa,i);
    30. 	}
    31. 	dp(0);
    32. 	printf("%d",f[0][m+1]);
    33. 	return 0;
    34. }

    路径求和

    给出一棵树，求出所有至少一个端点为叶节点的有向路径的权值和的和。

    1. #include
    2. using namespace std;
    3. #define int long long
    4. const int N=5e5+10;
    5. int n,m,root,tot,ans,cnt;
    6. int head[N],du[N],son[N],num[N];
    7. struct edge{int to,next,w;}e[N*2];
    8. int read()
    9. {
    10. 	int x=0,f=1;
    11. 	char ch=getchar();
    12. 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    13. 	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    14. 	return x*f;
    15. }
    16. void add_edge(int u,int v,int w)
    17. {
    18. 	e[++tot].to=v;
    19. 	e[tot].w=w;
    20. 	e[tot].next=head[u];
    21. 	head[u]=tot;
    22. }
    23. void dfs(int u,int fa)
    24. {
    25. 	num[u]=1;
    26. 	if(du[u]==1) cnt++,son[u]=1;
    27. 	for(int i=head[u];i;i=e[i].next)
    28. 	{
    29. 		int v=e[i].to;
    30. 		if(fa==v) continue;
    31. 		dfs(v,u);
    32. 		son[u]+=son[v];
    33. 		num[u]+=num[v];
    34. 	}
    35. }
    36. void find(int u,int fa)
    37. {
    38. 	for(int i=head[u];i;i=e[i].next)
    39. 	{
    40. 		int v=e[i].to;
    41. 		if(fa==v) continue;
    42. 		find(v,u);
    43. 		ans+=e[i].w*(son[v]*(n-num[v])+num[v]*(cnt-son[v]));
    44. 	}
    45. }
    46. signed main()
    47. {
    48. 	n=read(),m=read();
    49. 	for(int i=1;i<=m;i++)
    50. 	{
    51. 		int u,v,w;
    52. 		w=read(),u=read(),v=read();
    53. 		du[u]++;du[v]++;
    54. 		add_edge(u,v,w);
    55. 		add_edge(v,u,w);
    56. 	}
    57. 	dfs(1,0);find(1,0);
    58. 	printf("%lld",ans);
    59. 	return 0;
    60. }

    树上移动

    在给定的树上：

    一个人从 s 出发，求经过所有点的最短长度。
    两个人从 s 出发，走的路径没有限制，求经过所有点的最短长度。

    1. #include
    2. using namespace std;
    3. struct edge{int to,next,w;}e[500010];
    4. int n,m,sum,tot,f1[100010],f2[100010],head[100010];
    5. int read()
    6. {
    7. 	int x=0,f=1;
    8. 	char ch=getchar();
    9. 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    10. 	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    11. 	return x*f;
    12. }
    13. void add_edge(int u,int v,int w)
    14. {
    15. 	e[++tot].to=v;
    16. 	e[tot].w=w;
    17. 	e[tot].next=head[u];
    18. 	head[u]=tot;
    19. }
    20. void dfs(int u,int fa)
    21. {
    22. 	for(int i=head[u];i;i=e[i].next)
    23. 	{
    24. 		int v=e[i].to;
    25. 		if(fa==v) continue;
    26. 		dfs(v,u);
    27. 		if(f1[v]+e[i].w>f1[u])
    28. 		{
    29. 			f2[u]=f1[u];
    30. 			f1[u]=f1[v]+e[i].w;
    31. 		}
    32. 		else if(f1[v]+e[i].w>f2[u]) f2[u]=f1[v]+e[i].w;
    33. 	}
    34. }
    35. int main()
    36. {
    37. 	n=read(),m=read();
    38. 	for(int i=1;i
    39. 	{
    40. 		int u,v,w;
    41. 		u=read(),v=read(),w=read();
    42. 		add_edge(u,v,w);
    43. 		add_edge(v,u,w);
    44. 		sum+=w;
    45. 	}
    46. 	dfs(m,0);
    47. 	printf("%d\n",sum*2-f1[m]);
    48. 	int maxx=0;
    49. 	for(int i=1;i<=n;i++)
    50. 	{
    51. 		f1[i]+=f2[i];
    52. 		maxx=max(maxx,f1[i]);
    53. 	}
    54. 	printf("%d",sum*2-maxx);
    55. 	return 0;
    56. }

    块的计数

    给定一棵 n 个节点的树，每个点有个喜欢程度，要求选一个联通块，并且这个联通块包含最大的喜欢程度的方案数，输出的方案数对 998244353 取模。

    一个点也是联通块！！！正难则反，用联通块数减去不含最大值的联通块数，递归联通块数的时候用乘法原理就好。而且不保证点权为正，初始值赋0的话只有30pts/orz

    1. #include
    2. using namespace std;
    3. #define int long long
    4. const int N=100010;
    5. const int mod=998244353;
    6. int n,tot,mx,head[N],a[N],f[N],g[N],sum,ans;
    7. struct edge{int to,next;}e[N<<1];
    8. int read()
    9. {
    10.     int x=0,f=1;
    11.     char ch=getchar();
    12.     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    13.     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    14.     return x*f;
    15. }
    16. void add_edge(int u,int v)
    17. {
    18.     e[++tot].to=v;
    19.     e[tot].next=head[u];
    20.     head[u]=tot;
    21. }
    22. void dfs(int u,int fa)
    23. {
    24.     g[u]=1;
    25.     if(a[u]==mx) f[u]=0;
    26.     else f[u]=1;
    27.     for(int i=head[u];i;i=e[i].next)
    28.     {
    29.         int v=e[i].to;
    30.         if(fa==v) continue;
    31.         dfs(v,u);
    32.         f[u]=f[u]*(f[v]+1)%mod;
    33.         g[u]=g[u]*(g[v]+1)%mod;
    34.     }
    35.     sum=(sum+g[u])%mod;
    36.     ans=(ans+f[u])%mod;
    37. }
    38. signed main()
    39. {
    40.     n=read();mx=-1e18;
    41.     for(int i=1;i<=n;i++)
    42.     {
    43.         a[i]=read();
    44.         mx=max(mx,a[i]);
    45.     }
    46.     for(int i=1;i
    47.     {
    48.         int u=read();
    49.         int v=read();
    50.         add_edge(u,v);
    51.         add_edge(v,u);
    52.     }
    53.     dfs(1,0);
    54.     printf("%lld",(sum+mod-ans)%mod);
    55.     return 0;
    56. }

    权值统计

    给出一个 n 个结点的无根树以及每个结点的权值，求出树的每一条路径的权值积的和，单独的一个结点也算作一条路径。

    1. #include
    2. using namespace std;
    3. #define int long long
    4. const int mod=10086;
    5. int n,ans,a[100010],f[100010],head[100010],tot;
    6. struct edge{int to,next;}e[500010];
    7. void add_edge(int u,int v)
    8. {
    9. 	e[++tot].to=v;
    10. 	e[tot].next=head[u];
    11. 	head[u]=tot;
    12. }
    13. void dfs(int u,int fa)
    14. {
    15. 	int sum,tot;
    16. 	sum=tot=0;
    17. 	for(int i=head[u];i;i=e[i].next)
    18. 	{
    19. 		int v=e[i].to;
    20. 		if(fa==v) continue;
    21. 		dfs(v,u);
    22. 		sum+=f[v];
    23. 		tot+=f[v]*f[v];
    24. 	}
    25. 	f[u]=(sum+1)*a[u]%mod;
    26. 	ans+=f[u]+(sum*sum-tot)*a[u]/2%mod;
    27. 	ans%=mod;
    28. }
    29. signed main()
    30. {
    31. 	scanf("%lld",&n);
    32. 	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    33. 	for(int i=1;i< n;i++)
    34. 	{
    35. 		int u,v;
    36. 		scanf("%lld%lld",&u,&v);
    37. 		add_edge(u,v);
    38. 		add_edge(v,u);
    39. 	}
    40. 	dfs(1,0);
    41. 	printf("%lld",ans);
    42. 	return 0;
    43. }

    树的合并

    给定两棵树，则总共有 n*m 种方案把这两棵树通过加一条边连成一棵树，那这 n*m 棵树的直径大小之和是多少呢？树的直径指的是树上的最长简单路径。

    树的合并（ybtoj-树上dp）_wind__whisper的博客-CSDN博客_树的合并

  • 相关阅读:
    测试进阶知识之零日攻击的发现和防御
    VRRP虚拟路由器冗余协议
    包载信使mRNA的多西环素纳米脂质体|雷公藤红素纳米脂质体RNA核糖核酸（实验原理）
    java计算机毕业设计风情旅游网站源码+mysql数据库+系统+lw文档+部署
    搭建一个通用监控告警平台，架构上需要有哪些设计
    Workfine新手入门：分级预览
    第10章_索引优化与查询优化
    【ViT 微调时关于position embedding如何插值（interpolate）的详解】
    Hexagon_V65_Programmers_Reference_Manual（41）
    快速排序 sort
  • 原文地址：https://blog.csdn.net/m0_60137414/article/details/126587686