CF1363E Tree Shuffling

题意：Ashish has a tree consisting of n nodes numbered 1 to n rooted at node 1. The ii-th node in the tree has a cost a[i], and binary digit b[i] is written in it. He wants to have binary digit c[i] written in the i-th node in the end.

To achieve this, he can perform the following operation any number of times:

Select any k nodes from the subtree of any node u, and shuffle the digits in these nodes as he wishes, incurring a cost of k⋅a[u]. Here, he can choose k ranging from 1 to the size of the subtree of u.

He wants to perform the operations in such a way that every node finally has the digit corresponding to its target.

Help him find the minimum total cost he needs to spend so that after all the operations, every node u has digit c[u] written in it, or determine that it is impossible.

img

Examples

input1

1
2
3
4
5
6
7
8
9
10
5
1 0 1
20 1 0
300 0 1
4000 0 0
50000 1 0
1 2
2 3
2 4
1 5

output1

1
4

input2

1
2
3
4
5
6
7
8
9
10
5
10000 0 1
2000 1 0
300 0 1
40 0 0
1 1 0
1 2
2 3
2 4
1 5

output2

1
24000

显然可以观察到： 当一个节点拥有 0 需要 1 时，可以看作整体拥有一个 “0” 资源，对于 1 同理；

所以只有当两个相等是才是有解的。

可以观察到，当在某一个节点 u 操作时

1、此时的代价应为 u 到root 路径上最小代价，此时有两种方法，一是提前计算出在某节点操作的最小代价；二是将操作推迟到最小处再执行

2、当节点 u 的子节点操作后，该节点 u 所拥有的 0/1 个数是变化的，可以在递归回溯的时候更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
const int MAX=200000+10;
int n,u,v;
vi g[MAX];
ll a[MAX],b[MAX],c[MAX],vis[MAX],fa[MAX],m[MAX],ans=0;
void dfs(int u,ll _min){
	vis[u]=1;
	fi(i,0,g[u].size()){
		int v=g[u][i];
		if(vis[v]) continue;
		fa[v]=u;
		m[v]=min(m[v],_min);
		dfs(v,m[v]);
	}
} 
pii dfs2(int u){
	pii cnt;
	if(b[u]!=c[u]){
		if(b[u]) cnt.first++;
		else cnt.second++;
	}
	fi(i,0,g[u].size()){
		int v=g[u][i];
		if(v==fa[u]) continue;
		pii res= dfs2(v);
		cnt.first+=res.first;
		cnt.second+=res.second;
	}
	if(a[u]<=m[u]){
		int tmp =  min(cnt.first, cnt.second);
		ans += 2*tmp*a[u];
		cnt.first-=tmp;
		cnt.second-=tmp;
	}
	return cnt;
}
int main(){
//	freopen("in","r",stdin);
	sf(n);
	fi(i,1,n+1){
		scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
		m[i]=a[i];
	}
	fi(i,0,n-1){
		sf(u);sf(v);
		g[u].pb(v);	g[v].pb(u);
	}
	mem(vis,0);mem(fa,0);
	dfs(1,a[1]);
	pii res=dfs2(1);
	if(res.first||res.second){
		puts("-1");return 0;
	}
	printf("%lld",ans);
	return 0;
}