本文共 804 字，大约阅读时间需要 2 分钟。

题意：

给定n个点的树，每个点有一个权值a(i)，

数据范围：n<=1e5

解法：

题目给的是树,很容易往树形dp想,但是树形dp应该很难写,挺坑的.建立源点0,向n个点建立有向边,边权为-a[i],建立汇点n+1,n个点都向它有向边,边权为a[i],令原图的双向边边权取反变为负数,那么点0到点n+1的最短路就是式子的答案.

code：

#include
   
    using namespace std;const int maxm=1e5+5;int head[maxm],nt[maxm<<2],to[maxm<<2],w[maxm<<2],tot;int mark[maxm];int d[maxm];int a[maxm];int n;void add(int x,int y,int z){
       tot++;nt[tot]=head[x];head[x]=tot;to[tot]=y;w[tot]=z;}void spfa(int st){
       queue
    
     q;    q.push(st);    for(int i=1;i<=n+1;i++){
           d[i]=-1e9;        mark[i]=0;    }    d[st]=0;    mark[st]=1;    while(!q.empty()){
           int x=q.front();q.pop();        mark[x]=0;        for(int i=head[x];i!=-1;i=nt[i]){
               int v=to[i];            if(d[v]
    
   

转载地址：http://wdkv.baihongyu.com/