CF1061E Politics

我们思考一下这个问题的性质。因为限制是:子树内被标记的点的个数。同时子树内所有以有限制的点为根的子树,标记点数量都是确定的。所以我们发现,一个点x是否选择,对且只对一个点f的限制是否满足有影响,这个点f就是x在树上最近的有限制的父亲。所以我们把x是否选择交给f来决定。这种限制以及数据范围提示我们费用流。

建图就很好建了。对于每个有限制的点i,连边S>i1S-> i_1,费用为0容量为limii1lim_i-\sum i_1在子树内不能控制的点的已经确定的大小,另一边连边i2>Ti_2->T同理,容量调整为树2的限制即可。

我们现在已经满足了两棵树上所有限制点的合法(树1每个点流入,树2每个点流出的流量都等于他们各自控制的点集中选择了的点的个数)。然后我们考虑怎么把两棵树联系起来计算贡献。对于一个点i在树1和树2上的映射(i1,i2)(i1,i2),代表他们两个点是否选择的流量都在距离他们最近的有限制的父亲中,记为(fa1,fa2)(fa_1,fa_2)。那我们就连一条边fa1>fa2fa_1->fa_2,容量为1,费用为其贡献,这条边流过就代表选择点i,然后fa1,fa2fa_1,fa_2限制都要-1。

最后跑最大费用最大流即可。

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=2*505;
const int base=505;
const int S=maxn-2;
const int T=maxn-3;
int a[maxn];
vi ori[2][maxn];
int head[maxn],cnt=1;
struct gg{
	int u,v,w,cost,next;
}side[(maxn*3)*2+1000];
int size[2][maxn];
int lim[2][maxn];
int n,x,y,q1,q2;
int f[2][maxn];
void dfs1(int u,int fa,int floor){
	size[floor][u]=1;f[floor][u]=fa;
	rep(i,0,ori[floor][u].size()-1){
		int v=ori[floor][u][i];if(v==fa)continue;
		dfs1(v,u,floor);size[floor][u]+=size[floor][v];
	}
}
void ins(int u,int v,int w,int cost){
	side[++cnt]=(gg){u,v,w,cost,head[u]};head[u]=cnt;
	side[++cnt]=(gg){v,u,0,-cost,head[v]};head[v]=cnt;
//	cout<<u<<' '<<v<<' '<<cost<<endl;
}
int flag=-1;
int dfs2(int u,int fa,int floor){
	if(lim[floor][u]&&flag!=u)return lim[floor][u];
	int res=0;
	rep(i,0,ori[floor][u].size()-1){
		int v=ori[floor][u][i];if(v==fa)continue;
		res+=dfs2(v,u,floor);
	}
	return res;
}
ll ans;

int dis[maxn];
int inf=2e9;
queue<int>q;
int vis[maxn];
bool spfa(int s,int t){
	memset(dis,-0x3f,sizeof(dis));while(!q.empty())q.pop();
	dis[s]=0;vis[s]=1;q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int i=head[u];i;i=side[i].next){
			int v=side[i].v,val=side[i].cost;
			if(dis[u]+val>dis[v]&&side[i].w>0){
				dis[v]=dis[u]+val;
				if(!vis[v]){vis[v]=1;q.push(v);}
			}
		}
	}
	if(dis[t]<-1e8)return 0;
	return 1;
}
int cur[maxn];
int dfs3(int u,int flow){
	if(u==T)return flow;
	vis[u]=1;
	int used=0;
	for(int &i=cur[u];i&&used<flow;i=side[i].next){
		int v=side[i].v,w=side[i].w,cost=side[i].cost;
		if(!vis[v]&&dis[u]+cost==dis[v]&&w){
			int send=dfs3(v,min(w,flow-used));
			ans+=1ll*send*cost;
			side[i].w-=send;side[i^1].w+=send;used+=send;
		}
	}
	vis[u]=0;
	return used;
}
int mcfx(){
	int mxflow=0;
	while(spfa(S,T)){
		memcpy(cur,head,sizeof(cur));	
		mxflow+=dfs3(S,inf);
	}
	return mxflow;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>x>>y;
	rep(i,1,n)cin>>a[i];
	rep(i,1,n-1){int u,v;cin>>u>>v;ori[0][u].pb(v);ori[0][v].pb(u);}
	rep(i,1,n-1){int u,v;cin>>u>>v;ori[1][u].pb(v);ori[1][v].pb(u);}
	cin>>q1;rep(i,1,q1){int k;cin>>k;cin>>lim[0][k];}
	cin>>q2;rep(i,1,q2){int k;cin>>k;cin>>lim[1][k];}
	dfs1(x,0,0);dfs1(y,0,1);
//	if(!lim[0][x])lim[0][x]=inf;
//	if(!lim[1][y])lim[1][y]=inf;
	rep(i,1,n){
		flag=i;
		if(lim[0][i]){
			ins(S,i,lim[0][i]-dfs2(i,f[0][i],0),0);
			//ins(i,S,0,0);
		}
		if(lim[1][i]){
			ins(i+base,T,lim[1][i]-dfs2(i,f[1][i],1),0);
		//	ins(T,i+base,0,0);
		}
		flag=-1;
		int fa1=i,fa2=i;
		while(!lim[0][fa1]&&fa1!=x){fa1=f[0][fa1];}
		while(!lim[1][fa2]&&fa2!=y){fa2=f[1][fa2];}
		//cout
		ins(fa1,fa2+base,1,a[i]);
	//	ins(fa2+base,fa1,0,-a[i]);
	}
	mcfx();
	for(int i=head[S];i;i=side[i].next){
		if(side[i].w){cout<<"-1";return 0;}
	}
	for(int i=head[T];i;i=side[i].next){
		if(side[i^1].w){cout<<"-1";return 0;}
	}
	cout<<ans;
	return 0;
}