巳時，閑來無事，學分數(shù)規(guī)劃至正午，忽覺無用，遂大悲，閱洛谷題庫以尋題，欽四五題以切，遇此好題。

題意。

一棵 \(N\) 個點的樹，點權(quán)不是 0 就是 1。

我們有一個神秘的操作，我們先選擇一個點，把它和所有的相鄰點權(quán)都取反。

詢問最小的操作次數(shù)，使得所有的點權(quán)最后都為 0。

\(N\) 是 \(1e5\) 級別

做法

如果思考這個問題的特點，我們會發(fā)現(xiàn)這個東西跟順序是沒有關系的，因為我們?nèi)绻_定了某個點的操作次數(shù)，什么時候進行顯然都是一樣的。

于是我們可以通過子樹合并的順序進行，每次對父親產(chǎn)生的約束僅僅會向上一層，所以我們可以嘗試使用樹形dp.

怎么設計狀態(tài)？不難想到設 dp[u][0/1] 代表 \(u\) 子樹，不會/會 影響到父親的，保證樹中清空的最小操作次數(shù)。

然而這個樣子我們似乎并沒辦法去進行轉(zhuǎn)移，原因是我們不清楚何時進行操作，我們的轉(zhuǎn)移一定是基于我們進行的操作的。

既然不知道，我們便可以把這個東西設進狀態(tài)。

可以看出，一個點操作偶數(shù)次相當于沒操作，所以我們加一維 0/1 表示這個點經(jīng)歷了若干次操作 沒有/有 被改變。

對應的，dp 數(shù)組定義中需要加上所清空范圍不包含 u 節(jié)點。

理論上應該是能做了，先試著列一下轉(zhuǎn)移式子，有需要再進行添加。

\(v \in son[u]\)，我們掃到一個子樹，無非就是受不受影響，把這兩種情況列出來就好了。

\(dp_{u,0,0}\gets min_{v\in son[u]}(dp_{v,0,a_v}+dp_{u,0,0},dp_{v,1,a[v]}+dp_{u,0,1})\)

前者是不受影響，后者是受影響。

同理我們接著列就行了。

\(dp_{u,0,1}\gets min_{v\in son[u]}(dp_{v,0,a_v}+dp_{u,0,1},dp_{v,1,a[v]}+dp_{u,0,0})\)

\(dp_{u,1,0}\gets min_{v\in son[u]}(dp_{v,0,(1-a_v)}+dp_{u,1,0},dp_{v,1,(1-a[v])}+dp_{u,1,1})\)

\(dp_{u,1,1}\gets min_{v\in son[u]}(dp_{v,0,(1-a_v)}+dp_{u,1,1},dp_{v,1,(1-a[v])}+dp_{u,1,0})\)

打比較長的 Latex 能力較弱，應該沒什么大問題了。

考慮怎么初始化，實際很簡單，初始化什么都不動和修改一下就行，其它情況等著轉(zhuǎn)移上來。

就是 dp[u][0][0]=0, dp[u][1][1]=1, dp[u][1][0]=dp[u][0][1]=0x3f3f3f3f;

之后還需要注意我們的轉(zhuǎn)移可能會出現(xiàn)問題，直接這么寫會出環(huán)。

每一次進行轉(zhuǎn)移的時候我們使用 tmp[2][2] 存一下 dp[u][2][2] 的值，里邊用這個進行轉(zhuǎn)移就沒問題了。

代碼↓

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
struct Node{
	int nxt, to;
}node[MN];
int head[MN], tottt;
void insert(int u, int v){
	node[++tottt].to=v;
	node[tottt].nxt=head[u];
	head[u]=tottt; return;
}
int a[MN], n, dp[MN][2][2], ans;
void dfs(int u, int father){
	bool isleaf=true;
	dp[u][0][0]=0; dp[u][1][1]=1;
	dp[u][1][0]=1e10;
	dp[u][0][1]=1e10;
	for(int i=head[u];i;i=node[i].nxt){
		int v=node[i].to;
		if(v==father) continue;
		dfs(v,u); isleaf=false;
	}
	for(int i=head[u];i;i=node[i].nxt){
		int v=node[i].to;
		if(v==father) continue;
		int tmp[2][2];
		tmp[0][0]=dp[u][0][0];
		tmp[0][1]=dp[u][0][1];
		tmp[1][1]=dp[u][1][1];
		tmp[1][0]=dp[u][1][0];
		dp[u][0][0]=min(tmp[0][0]+dp[v][0][a[v]],tmp[0][1]+dp[v][1][a[v]]);
		dp[u][0][1]=min(tmp[0][1]+dp[v][0][a[v]],tmp[0][0]+dp[v][1][a[v]]);
		dp[u][1][0]=min(tmp[1][0]+dp[v][0][(1-a[v])],tmp[1][1]+dp[v][1][(1-a[v])]);
		dp[u][1][1]=min(tmp[1][1]+dp[v][0][(1-a[v])],tmp[1][0]+dp[v][1][(1-a[v])]);
	}
	if(u==1){
		ans=min(dp[1][0][a[1]],dp[1][1][a[1]]);
	}
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n;
	for(int i=1,u,v; i<n; ++i){
		cin>>u>>v; insert(u,v); insert(v,u);
	}
	for(int i=1; i<=n; ++i) cin>>a[i];
	dfs(1,1);
	if(ans>=1e10) cout<<"impossible\n";
	else cout<<ans<<'\n';
	return 0;
}