An electrical grid in Berland palaces consists of 2 grids: main and reserve. Wires in palaces are made of expensive material, so selling some of them would be a good idea!
Each grid (main and reserve) has a head node (its number is 1). Every other node gets electricity from the head node. Each node can be reached from the head node by a unique path. Also, both grids have exactly n nodes, which do not spread electricity further.
In other words, every grid is a rooted directed tree on n leaves with a root in the node, which number is 1. Each tree has independent enumeration and nodes from one grid are not connected with nodes of another grid.
Also, the palace has n electrical devices. Each device is connected with one node of the main grid and with one node of the reserve grid. Devices connect only with nodes, from which electricity is not spread further (these nodes are the tree's leaves). Each grid's leaf is connected with exactly one device.
In this example the main grid contains 6 nodes (the top tree) and the reserve grid contains 4 nodes (the lower tree). There are 3 devices with numbers colored in blue.
It is guaranteed that the whole grid (two grids and 𝑛 devices) can be shown in this way (like in the picture above):
main grid is a top tree, whose wires are directed 'from the top to the down',
reserve grid is a lower tree, whose wires are directed 'from the down to the top',
devices — horizontal row between two grids, which are numbered from 1 to 𝑛 from the left to the right,
wires between nodes do not intersect.
Formally, for each tree exists a depth-first search from the node with number 1, that visits leaves in order of connection to devices 1,2,…,𝑛 (firstly, the node, that is connected to the device 1, then the node, that is connected to the device 2, etc.).
Businessman wants to sell (remove) maximal amount of wires so that each device will be powered from at least one grid (main or reserve). In other words, for each device should exist at least one path to the head node (in the main grid or the reserve grid), which contains only nodes from one grid.
链接🔗
「CodeForces 1263F」Economic Difficulties
题解
，考虑DP做法,,表示第 棵树将 区间断电最多能删除多少边
然后用来维护该节点维护下面覆盖了那些子节点，最后再用DP合并一些即可
代码
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
using namespace std;
const int maxd = 2e3+10;
vector<int> G[2][maxd];
int dp[maxd],v[2][maxd][maxd],l[2][maxd],r[2][maxd],sz[2][maxd];
// L[i]，R[i]表示将盖以i节点为根子树删掉，最多能使得[L,R]区间内的发电机停电
int n,a;
void dfs(int id,int x)
{
if(x!=1) sz[id][x] = 1; // N个点n-1条边，根节点无父边
for(int v :G[id][x])
{
dfs(id,v);
l[id][x] = min(l[id][x],l[id][v]);
r[id][x] = max(r[id][x],r[id][v]);
sz[id][x] += sz[id][v];
}
int ll = l[id][x],rr = r[id][x];
v[id][ll][rr] = max(v[id][ll][rr],sz[id][x]); // 代价是该子树的大小
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("k.out","w",stdout);
int n;scanf("%d",&n);
for(int t=0;t < 2;t++)
{
int m;scanf("%d",&m);
for(int i=1;i<=m;i++)
{
l[t][i] = m+1;
r[t][i] = 0;
}
for(int i=2;i<=m;i++)
{
int x; scanf("%d",&x);
G[t][x].push_back(i);
}
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);
l[t][x] = r[t][x] = i;
}
dfs(t,1);
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
dp[j] = max(dp[j], dp[i-1] + max(v[0][i][j],v[1][i][j]));
printf("%d\n",dp[n]);
return 0;
}