图论中树上dp有关问题

Question

请问下面问题如何用C++解决？（时间复杂度最大nlogn)

题目描述

李大枕头要和金人老板进行最后的对决，他们打算通过一款名叫《谁是大赢家》的游戏决出胜负。（让我连线，我现在就要连线）

游戏以金人巷作为地图，金人巷有$n$家商铺，这些商铺之间有一些供给关系，比如商铺$x$的原料由商铺$y$供应，如果李大枕头占据了商铺$y$，金人老板占据了商铺$x$，则对于这两家商铺之间，李大枕头小胜一筹；进一步地，若$x$又将原料供应给$t$，金人老板占据了$t$的话，李大枕头就可以通过控制$y$对$x$的原料供给来限制$t$的发展，对于$y,t$之间，李大枕头也胜一招。

若将商铺之间的供应关系，$y$供应给$x$,看做是图论关系，恰巧这些商铺的关系组成了一棵树。即，每家商铺（除了编号1）都有且仅有一家商铺提供原料。

二人进行的是回合制游戏，李大枕头和金人老板依次买下一间商铺，每家商铺购买需要花费$w[i]$。假设李大枕头购买了某家商铺$x$，对方有$n1$家商铺的原料是被$x$所限制的，同时对方有$n2$家商铺能够通过供应限制$x$，若$n1>n2$，则李大枕头获利$n1-n2$；若$n1<n2$，则李大枕头这次购买比较失败，要赔给对方$n2-n1$。

不能重复购买，且两人都是仙舟绝顶聪明之人，请问$\frac{n}{2}$轮后，李大枕头获利最多是多少？（可能为负数）

输入格式

输入文件 c.in

第一行一个正整数 $n$。

第二行 $n$ 个非负整数，第 $i$ 个整数为 第$i$个商铺 的价格 $w_i$。

第三行 $n-1$ 个正整数，第 $i$ 个正整数表示第 $i+1$ 个商铺的父亲节点编号。

输出格式

输出文件 c.out

一行一个整数表示答案。

Answer 1

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7471289
• 除此之外, 这篇博客: 单素数判断（根号n后再优化）和俄罗斯农民乘法(带证明），以及埃筛的证明中的 简单解释下普遍大家都知道的（给新手），就是为啥只到根号n。最开始其实终止条件是到n/2的，很简单嘛，因为n/2之后不可能存在n的因子，因为最小的因子2乘上一个任何一个大于n/2的数肯定比n大，所以之后不存在因子。那为啥能筛到根号n呢，是因为根号n的平方是n本身，根号n后面如果存在n的因子a，那么一定能在n之前找到n/a这个因子，只要有因子就不是素数了，所以没必要反复筛，前面筛完就已经知道不是素数了 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

  #include<bits/stdc++.h>
  using namespace std;
  int main() 
  {
  	int n;
  	cin>>n;
  	if(n==2||n==3)
  	{
  		cout<<"是素数";
  	}
  	else if(n%6!=1&&n%6!=5)
  	{
  		cout<<"不是素数";
  	}
  	else
  	{
  		for(int i=2;i*i<=n;i++)
  		{
  			if(!(n%i))
  			{
  				cout<<"不是素数" ;
  				return 0;
  			}
  		}
  		cout<<"是素数";
  	}
  }
  

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^