Codeforces Round #603 F Economic Difficulties

题目大意

给你两棵树，结点分别是1～A与1～B，然后给了N台设备，并且A树和B树的叶子结点(两棵树的叶子节点数量相同)都是链接电机的。问，最多可以删掉几条边使得每个设备都能连到任意一棵（或两棵）树的根节点（1号点）

思路

对于每棵树，维护\(val[cnt][i][j]\)，\(cnt\)是那个树表示我删掉这个子树的所有边之后，\([i,j]\)这个范围的设备不保证能够全部连上我的根。

用一个\(f[i]\)表示\([1,i]\)区间内，全都能连上根最多能删除多少条边，那么转移就是\(f[i]=max(f[i],f[j-1]+max(val[cnt][j][i]))\)

代码

#include<bits/stdc++.h>

#include<vector>

using namespace std;

const int N=2019;

vector<int> G[2][N];

int f[N];

int val[2][N][N],l[2][N],r[2][N],size[2][N];

int x,n,a;

void dfs(int num,int x)

{

	if(x!=1) size[num][x]=1;

	for(int i=0;i<G[num][x].size();++i)

	{

		int to=G[num][x][i];

		dfs(num,to);

		size[num][x]+=size[num][to];

		l[num][x]=min(l[num][x],l[num][to]);

		r[num][x]=max(r[num][x],r[num][to]);

	}

	val[num][l[num][x]][r[num][x]]=max(val[num][l[num][x]][r[num][x]],size[num][x]);

}

void read() {

	cin>>n;

	for(int cnt=0; cnt<=1; ++cnt) {

		cin>>a;

		for(int i=1; i<=a; i++) l[cnt][i]=a+1,r[cnt][i]=0;

		for(int i=2; i<=a; ++i) {

			cin>>x;

			G[cnt][x].push_back(i);

		}

		for(int i=1; i<=n; ++i) {

			cin>>x;

			l[cnt][x]=r[cnt][x]=i;

		}

		dfs(cnt,1);

	}

}

int main() {

	read();

	for(int i=1;i<=n;++i)

		for(int j=i;j<=n;++j)

			f[j]=max(f[j],f[i-1]+max(val[0][i][j],val[1][i][j]));

	cout<<f[n];

	return 0;

}

推荐看看这篇博客传送门

巴特西

Codeforces Round #603 F Economic Difficulties

题目大意

思路

代码

最新文章

热门文章