CF1061E - Politics

题目大意

给定两棵有根树$T_1,T_2$，节点均从$1-n$编号

对于节点$i$，有权值$a_i$，每个节点可以被选择一次

对于$T_1,T_2$，有$q_1,q_2$条限制，每条限制了一个子树$k$内恰好有$x$个点被选择

求最大化选择的权值之和，或者确定不存在方案


分析

如果剥离树的结构考虑，让问题变成点集之和的限制

这是一个经典的无法处理的问题，或许可以单纯形试试看

那么考虑树的结构如何处理

我们认为一个点被选择会向祖先链上的点总和+1，这是一个链状更新

可以用一棵内向树描述，再将限制加在边上，就能够得到一个简单的网络流模型

然而边权无法限制满流（除非上下界网络流），而现在问题不仅带权，还同时涉及两棵树

因此引入费用是必须的

解决恰好为$x$的限制

考虑将有限制的边视作特殊，我们将这条边额外加上一个费用$\infty$，最后从答案中减去

如果最优解中无法流满这些边，答案将$<0$


解决两棵树

Naive的思路，我们需要强制两棵树上同编号的点入流相同

经过长时间弱智的思考，这无法实现

于是想办法强制两个点入流不同

容易发现，对于被选个数的限制可以对称转化为限制未选个数

从源点$S$向$i_0$连一条流量为1的边，$i_0$流向$i_1$表示选择$i$，流向$i_2$表示不选

将$T_1$建成选择点的限制，$T_2$建成不选点的限制即可


形式化的说，对于一个费用流，我们想要限制两条边$flow_1=flow_2$

即$flow_1-flow_2=0$，这难以做到

但是我们可以限制$flow_1+(-flow_2)=0$，或者说

$flow_1+(w-flow_2)=w$

并且将对于$flow_2$的限制转化为对$w-flow_2$的限制，此时额外建立一个点$t$

$S$向$t$连$(w,\infty)$，强制向$t$流满$w$的流量，然后再从$t$向$flow_1,w-flow_2$分流即可


$\text{EK}$费用流 QQ图片20210506190147.jpg

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1544,INF=1e9+7;

int n,m,d;
int a[N];
struct Edge{
	int to,nxt,w,c;
} e[N*4];
int head[N],ecnt=1;
void AddEdge(int u,int v,int w,int c){
	e[++ecnt]=(Edge){v,head[u],w,c};
	head[u]=ecnt;
}
void Link(int u,int v,int w,int c){ AddEdge(u,v,w,c),AddEdge(v,u,0,-c); }
int S=1,T=2,V=2;

ll ans=0;
struct Tree{
	vector <int> G[N];
	int Rt,sz[N],lim[N],fa[N];
	void dfs(int u,int f) {
		//cout<<"pre dfs "<<u<<endl;
		sz[u]=1,lim[u]=-1,fa[u]=f;
		for(int v:G[u]) if(v!=f) {
			dfs(v,u);
			sz[u]+=sz[v];
		}
	}
	void ReadTree(){
		rep(i,2,n){
			int u=rd(),v=rd();
			G[u].pb(v),G[v].pb(u);
		}
		dfs(Rt,0);
	}
	void ReadLimit(){
		rep(_,1,rd()) {
			int u=rd(),x=rd();
			//cout<<"$"<<sz[u]<<endl;
			if(sz[u]<x) puts("-1"),exit(0);
			lim[u]=x;
		}
	}
	void Init(int k){
		fa[Rt]=T-V;
		if(k==0) {
			rep(i,1,n) {
				Link(T+i,V+i,1,a[i]);
				if(~lim[i]) {
					ans-=1ll*lim[i]*INF;
					Link(V+i,V+fa[i],lim[i],INF);
				} else Link(V+i,V+fa[i],n,0);
			}
		} else {
			rep(i,1,n) {
				Link(T+i,V+i,1,0);
				if(~lim[i]) {
					ans-=1ll*(sz[i]-lim[i])*INF;
					Link(V+i,V+fa[i],sz[i]-lim[i],INF);
				} else Link(V+i,V+fa[i],n,0);
			}
		}
		V+=n;
	}
} Tr[2];

ll dis[N];
int vis[N],pre[N];
int SPFA(){
	static queue <int> que;
	rep(i,1,V) dis[i]=-1e18;
	que.push(S),dis[S]=0;
	while(!que.empty()) {
		int u=que.front(); que.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to,c=e[i].c;
			if(dis[v]>=dis[u]+c || !e[i].w) continue;
			dis[v]=dis[u]+e[i].c,pre[v]=i;
			//cout<<"$"<<u<<' '<<v<<' '<<e[i].c<<' '<<e[i].w<<endl;
			if(!vis[v]) vis[v]=1,que.push(v);
		}
	}
	return dis[T]>-1e18;
}

void EK(){
	while(SPFA()) {
		int w=INF;
		for(int u=T;pre[u];u=e[pre[u]^1].to) cmin(w,e[pre[u]].w);
		for(int u=T;pre[u];u=e[pre[u]^1].to) e[pre[u]].w-=w,e[pre[u]^1].w+=w;
		ans+=w*dis[T];
	}
}

int main(){
	n=rd(),Tr[0].Rt=rd(),Tr[1].Rt=rd();
	rep(i,1,n) Link(S,V+i,1,INF),ans-=INF;
	V+=n;
	rep(i,1,n) a[i]=rd();
	rep(i,0,1) Tr[i].ReadTree();
	rep(i,0,1) Tr[i].ReadLimit(),Tr[i].Init(i);
	EK();
	if(ans<0) puts("-1");
	else printf("%lld\n",ans);
}