[Acwing] 4381. 翻转树边 树形dp

前言

传送门 :

思路

考虑树形 d p dp dp , 状态表示 d p [ i ] dp[i] dp[i]以 i i i为中心点的最小翻转次数

如果当前点为中心点 , 考虑两个方面 向上走 和 向下走

优先考虑向下走 :

我们可以递归到底层,自下向上的 d p dp dp

d p [ u ] + = d p [ v ] + w dp[u] +=dp[v]+w dp[u]+=dp[v]+w( w w w如果是正边那么设立为 0 0 0否则 1 1 1

然后我们考虑向上走 :

我们考虑 d p [ 4 ] = d p [ 4 ] + d p [ 2 ] − d p [ 4 ] + w ? − 1 : 1 dp[4] = dp[4]+dp[2] -dp[4]+w?-1:1 dp[4]=dp[4]+dp[2]−dp[4]+w?−1:1 当前的节点 4 4 4一定是子树 d p [ 4 ] dp[4] dp[4]+往上的集合 d p [ 2 ] dp[2] dp[2]，减去重复的 d p [ 4 ] dp[4] dp[4] 然后对于当前的边,如果是正边,但是对于 4 4 4来说，往上走是反边,所以需要 + 1 +1 +1,否则 − 1 -1 −1

因此 : 状态转移 : 第一次 : (求子树 d p [ u ] = d p [ v ] + w dp[u] =dp[v]+w dp[u]=dp[v]+w 第二次 : (求整个集合 d p [ v ] = d p [ u ] + w ? − 1 : 1 dp[v] = dp[u]+w?-1:1 dp[v]=dp[u]+w?−1:1

Code

const int N  = 4e5+10 , INF =  0x7fffffff;

struct node{
	int to,val;
};
vector g[N];

int f[N];


int minn = INF;


void dfs(int u,int fa){
	for(auto j : g[u]){
		if(j.to !=fa){
			dfs(j.to,u);
			f[u] += f[j.to] + j.val;
		}
	}	
}

void dfs_up(int u,int fa){
	for(auto j : g[u]){
		if(j.to != fa){
			f[j.to] = f[u] + (j.val?-1:1);
			dfs_up(j.to,u);
		}
	}
}




void solve()
{
	int n;cin>>n;
	for(int i=1;i>a>>b;
		g[a].pb({b,0});
		g[b].pb({a,1});
	}
	
	dfs(1,0);
	dfs_up(1,0);
	
	for(int i=1;i