换根dp 2024.12.29

啊啊啊啊啊.

其实和普通的dp差别不大，推了dp方程就是套模版

CF219Dlink

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=4e5+110;
int read(){
	int sum=0,k=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')k=-1;c=getchar();}
	while(c>='0'&&c<='9'){sum=sum*10+c-'0',c=getchar();}
	return sum*k;
}
struct w{int next,to,val;}e[M];
int head[M],k=0;
void add(int u,int v,int w){
	e[++k].next=head[u];
	e[k].to=v;
	e[k].val=w;
	head[u]=k;
}
int n,dp[M],minn=0x3f3f3f3f;
void dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].next)if(e[i].to!=fa)
		dfs(e[i].to,u),dp[u]+=e[i].val+dp[e[i].to];
}
void ans_dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].next) if(e[i].to!=fa){
		if(e[i].val==0) dp[e[i].to]=dp[u]+1;
		else dp[e[i].to]=dp[u]-1;
		ans_dfs(e[i].to,u);
	}
}
signed main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v,0),add(v,u,1);
	}
	dfs(1,0),ans_dfs(1,0);
	for(int i=1;i<=n;i++) if(dp[i]<minn) minn=dp[i];
	printf("%lld\n",minn);
	for(int i=1;i<=n;i++) if(dp[i]==minn) printf("%lld ",i);
	return 0;
}
/*
3
2 1
2 3
*/
/*
4
1 4
2 4
3 4
*/

然后来拆+解析这分代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=4e5+110;
int read(){
	int sum=0,k=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')k=-1;c=getchar();}
	while(c>='0'&&c<='9'){sum=sum*10+c-'0',c=getchar();}
	return sum*k;
}

这段是快读+取宏定义

struct w{int next,to,val;}e[M];
int head[M],k=0;
void add(int u,int v,int w){
	e[++k].next=head[u];
	e[k].to=v;
	e[k].val=w;
	head[u]=k;
}

链式前向星

void dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].next)if(e[i].to!=fa)
		dfs(e[i].to,u),dp[u]+=e[i].val+dp[e[i].to];
}
void ans_dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].next) if(e[i].to!=fa){
		if(e[i].val==0) dp[e[i].to]=dp[u]+1;
		else dp[e[i].to]=dp[u]-1;
		ans_dfs(e[i].to,u);
	}
}

两遍dfs

通常情况下第一遍dfs是解决以一个节点为根的一种情况

相当于初始化

本题是求有多少条反转道路，就相当于求每个节点为根时子树的道路反转数量

而一般换根dp还可以维护deep，用out[],in[],来作欧拉序与dfs序

第二个dfs

把状态转移方程推出来，就没有然后了

主函数也挺短的，这题就是建双向边，没有的那条就要反转，边权就是1

All in all

换根dp码量少，解决问题目的性强，应该好做要认真思考，然后推方程

给个大致思路 初始化->dp方程->没了

就是要多做然后秒个方程就好了

eggggggggg题:

1. poj3321 code

2.lg1087 code

3.lg3478 code

4.CF1187E code xxlg

5.lg2986 code

6.CF219D code xxlg

7. lg3047 code

8.CF1324F code xxlg

9.CF708C code xxlg