match 题解

[张瑜]

match 题解

题目大意：

思路概述：

这道题其实就是一道反悔贪心，就是先贪心选最大的，然后在另外颜色加一个负的就可以了。然后每次从子结点去往父节点的元素都去掉边权即可。其实不难，但是写起来需要用优先队列和 vector 。

代码部分

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
long long n,ma,mb,a[N],b[N];
priority_queue<long long> que[N][2];
vector<pair<long long,long long>> G[N];
long long ans;
void dfs(long long u,long long fa)
{
	for(auto[v,w]:G[u])
	{
		if(v^fa)
		{
			dfs(v,u);
			for(long long i:{0,1})
				while(!que[v][i].empty()) 
					que[u][i].push(que[v][i].top()-w),que[v][i].pop();
		}	
	}
	while(!que[u][0].empty()&&!que[u][1].empty()){
		long long t1=que[u][0].top(),t2=que[u][1].top();
		if(t1+t2>0){
			ans+=t1+t2;
			que[u][0].pop();
			que[u][1].pop();
			que[u][0].push(-t2);
			que[u][1].push(-t1);
		}
		else 
			break;
	}
}
int main()
{
	//freopen("ex_match.in","r",stdin);
	//freopen("1.out","w",stdout);
	cin>>n>>ma>>mb;
	for(long long i=1;i<=ma;i++) 
		cin>>a[i];
	for(long long i=1;i<=ma;i++)
	{
		long long x; 
		cin>>x;
		que[a[i]][0].push(x);
	}
	for(long long i=1;i<=mb;i++) 
		cin>>b[i];
	for(long long i=1;i<=mb;i++) 
	{
		long long x;
		cin>>x;
		que[b[i]][1].push(x);
	}
	for(long long i=1;i<n;i++)
	{
		long long u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	dfs(1,0);
	cout<<ans;
}