洛谷 P3574 [POI2014]FAR-FarmCraft

题目传送门

题目描述

输入输出格式

输入格式：

输出格式：

一行，包含一个整数，代表题目中所说的最小时间。

输入输出样例

样例输入

样例输出

提示

分析

我们设f[x]为遍历完以x为根的子树且将这棵子树上所有的电脑都安装完毕最终又回到x的最小安装时间

对于一棵子树，根节点所需要的安装时间自然是它本身的价值

那么各个子节点的价值可以直接拿来用吗？显然是不可以的

因为你从根节点遍历到子节点需要花费时间

所以这时就有遍历优先级的问题了

我们是先遍历安装时间最长的子树吗？这样是不可以的，比如下面这幅图

那我们该怎么办呢，我们可以发现，

代码

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int maxn=;

 struct Edge{

     int next,to;

 }e[maxn];

 int head[maxn],len;

 void Ins(int a,int b){

     e[++len].to=b;e[len].next=head[a];head[a]=len;

 }

 struct Node{

     int f,siz;

     Node(){}

     Node(int a,int b){f=a,siz=b;}

     bool operator < (const Node&A)const{

         return f-siz<A.f-A.siz;

     }

 };

 int dp[maxn],g[maxn],val[maxn],que[maxn];

 void dfs(int u,int fa){

     priority_queue<Node> q;

     if(u-)dp[u]=val[u];

     for(int i=head[u];i!=-;i=e[i].next){

         int v=e[i].to;

         if(v==fa)continue;

         dfs(v,u);q.push(Node(dp[v],g[v]));

     }

     while(!q.empty()){

         Node now=q.top();q.pop();

         dp[u]=max(dp[u],now.f+g[u]+);

         g[u]+=now.siz+;

     }

 }

 int main(){

     memset(head,-,sizeof(head));

     int n;

     scanf("%d",&n);

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

         scanf("%d",&val[i]);

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

         int a,b;

         scanf("%d%d",&a,&b);

         Ins(a,b);Ins(b,a);

     }

     dfs(,);

     printf("%d\n",max(dp[],val[]+g[]));

     return ;

 }

巴特西