TIMI tree / [BZOJ2031] pruning DP

[problem description]

There are many Timmy trees in Temmie village, which are covered with Temmie flakes. One day, Flowey came
Temmie village is a guest. Temmies want to give it a Timmy tree.
For this TIMI tree, the following properties are satisfied:
·1. This tree can be regarded as an undirected acyclic graph with n points, and a certain number of trees grow on each point
Temmie flakes. The number of flakes is recorded as the weight of this point. These points are marked as an integer from 1 to n
The middle point 1 is the root of the tree, and the point without children is the leaf on the tree.
·2. Depth first search is carried out for this tree, and each point traverses each child in order from left to right
DFS order to this tree.
·3. Definition (a,b) is a pair of adjacent leaves if and only if there are no other leaf nodes on the DFS order
a. B between. Each pair of adjacent leaves will produce a cost, which is on the path from a to B (excluding a and b)
Of the points, the maximum point weight.
·4. Timmy tree can provide determination. The amount of determination a TIMI tree can provide is on all the leaves on the tree
The sum of the number of long Temmie slices, minus the cost of all adjacent leaves.
Although Flowey is not a creature that feeds on Temmie flakes, it needs determination. This Timmy tree
There was so little determination to offer that temmies decided to prune the tree several times (without pruning) to make it
This tree can provide the most determination.
If you can cut all the leaves of a child at once.

[input format]

From temmie Read data in.
The first line of input data is a positive integer n, which represents the number of points on the Timmy tree.
Next n lines, for each line:
The first number is a positive integer representing the number of Temmie slices at this point
The second number is an integer num, which represents the number of children at this point
Next, the number of num represents the children from left to right of this point in turn.

[output format]

Output to temmie Out
The output contains a number, the maximum number of resolutions that can be provided after pruning the tree.

[example input 1]

3
1 2 2 3
2 0
2 0

[sample output 1]

3

[example input 2]

5
1 2 2 3
2 1 4
3 1 5
4 0
5 0

[sample output 2]

6

thinking

  • About the two key properties of this problem /?:
  • 1. Note that the extremum on the path of each two adjacent leaf nodes is calculated here. The complexity of multiplication is nlogn, but the complexity of just traversing the whole tree is O(n) by violent dfs;
  • 2. Regardless of pruning, two leaves that are not adjacent before pruning will not be adjacent [!] after pruning
  • dp[i] represents the answer to node i, and preliminarily write the dp equation: dp[x]=dp[y]-max(h[x],H[y])+num[x], where h[x] is the maximum value from X to lca, and H[y] is the same
  • It is found that this dp equation enumerates each pair of h[x], H[y], and the time complexity is n ^ 2 (not / but not...) Timeout 100%, think of the optimization time
  • Think of prefix optimization. Similar to prefix and, the maximum value of prefix (however, you can't think of it)
  • It should also be the monotonic increment of the h array after the maximum prefix value. It is thought that the double ended queue [routine] will reduce the complexity to O(n)
  • The idea seems very complex, but the implementation is slightly simple. See the code for specific comments

code

#include <iostream>
#include <cstdio>
#define inf 0x7f7f7f7f
#define maxn 100005
using namespace std;
int n,fa[maxn],head[maxn],cnt,keep[maxn],deep[maxn],w[maxn],e[maxn],h[maxn],H,num[maxn],dp[maxn],g[maxn],tmax;
struct fdfdfd{int next,to;}a[maxn];
void addedge(int x,int y){a[++cnt].to=y; a[cnt].next=head[x]; head[x]=cnt;}
int max(int a,int b){return a>b?a:b;}
void dfs(int x)
{
	deep[x]=deep[fa[x]]+1;
	if(!head[x]) keep[++cnt]=x;
	else for(int i=head[x];i;i=a[i].next) dfs(a[i].to);
}
int main()
{
	scanf("%d",&n);
	for(int i=1,tnum;i<=n;++i)
	{
		scanf("%d%d",&num[i],&tnum);
		for(int j=1,ch;j<=tnum;++j) scanf("%d",&ch),addedge(i,ch),fa[ch]=i;
	}
	cnt=0; dfs(1);//One pass dfs stores all leaf nodes of the tree
	int x=keep[1],y;
	while(x) dp[x]=num[x],x=fa[x];//Initialize the value of the first chain, dp[x]=num[x];
	for(int i=2;i<=cnt;++i)
	{
		w[0]=e[0]=0; x=keep[i]; y=keep[i-1];//w. e. record the points on the path from x and y to lca
		while(deep[x]>deep[y]) w[++w[0]]=x,x=fa[x];
		while(deep[y]>deep[x]) e[++e[0]]=y,y=fa[y];
		while(x!=y)
		{
			w[++w[0]]=x,x=fa[x];
			e[++e[0]]=y,y=fa[y];
		}//Note that from w[0]~1 record to leaf node, e is the same
		g[0]=h[e[0]+1]=H=tmax=-inf; int r=e[0];
		for(int j=e[0];j;--j) h[j]=max(h[j+1],num[fa[e[j]]]);//Prefix maximum [Supplement 1]
		for(int j=1;j<=e[0];++j) g[j]=max(g[j-1],dp[e[j]]-h[j]);//Here g is a part of dp transfer in for. If you don't understand it, skip it first
		for(int j=w[0];j;--j)
		{
			H=max(H,num[fa[w[j]]]);//Omit the H array and find it directly each time
			while(r&&H>h[r]) tmax=max(tmax,dp[e[r--]]);//Find the last node less than H on e
			dp[w[j]]=max(tmax-H,g[r])+num[w[j]];//[Supplement 2]
		}
	}
	x=keep[cnt]; int ans=-inf;
        while(x) ans=max(dp[x],ans),x=fa[x];
        printf("%d\n",ans);
	return 0;
}
//[Supplement 1]: when you don't understand why when reading some problem solving codes fa[e[j]], you find that "the cost is on the path from a to B (excluding a,b)"...
//[supplementary 2]: in Max, tmax-H is the maximum value of dp[y]-max(h[x],H[y]) when h array < h, and g[r] is the maximum value when h array > H,
//It also explains why we need to find the g array in advance instead of using dp[e[r]]-h[r]

Tags: tree dp

Posted by Steven_belfast on Wed, 18 May 2022 16:28:49 +0300