加载中…
个人资料
鈞少
鈞少
  • 博客等级:
  • 博客积分:0
  • 博客访问:32,758
  • 关注人气:17
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

SOJ  3925  (The Weight of Tree)树形DP

(2012-10-26 11:19:32)
标签:

杂谈

= = !!这OJ还是第一次上 , 不知道队友哪里刮到这题的 。
简单的树形DP ,感觉就是连续最大子序列的树形版本 ,看完题瞬间秒掉了~
dp存的就是当前点的最优解 , 转移方程就不多介绍了 。

#include <iostream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>

using namespace std;

#define ll long long

typedef struct
{
int u,v,val,next;
}element;

element edge[100100<<1]; 
int n;
int head[100100];
int pre = 0;
bool vis[100100];
int values[100100];
int dp[100100];
int maxer[100100];
 
inline void addedge(int u , int v )
{
//edge[pre].u = u;
edge[pre].v = v;
//edge[pre].val = val;
edge[pre].next = head[u];
head[u] = pre++;
swap(u,v);
//edge[pre].u = u;
edge[pre].v = v;
//edge[pre].val = val;
edge[pre].next = head[u];
head[u] = pre++;
}

void dfs(int idx , int fa)
{
vis[idx] = 1;
//dp[idx] = values[idx];
//maxer[idx] = values[idx];
for(int i = head[idx] ; i != -1 ; i = edge[i].next)
{
int v = edge[i].v;
if(v == fa)continue;
if(!vis[v])
{
dfs(v , idx);
if(dp[v] < 0)continue;   //  小于0的不要   大于0的统计 
dp[idx] = max(dp[idx] , dp[v] + dp[idx]);
}
}
}


int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(head , -1 , sizeof(head));
memset(vis , 0 , sizeof(vis));
//memset(maxer , 0 , sizeof(maxer));
pre = 0;
for(int i = 1 ; i <= n ; ++i)
scanf("%d",&dp[i]);//scanf("%d",&values[i]);
for(int i = 0 ; i < n - 1 ; ++i)
{
int a,b;
scanf("%d%d",&a,&b);
addedge(a,b);
}
dfs(1 , -1);
int ans = -9999999 ;
for(int i = 1 ; i <= n ; ++i)
ans = max(ans , dp[i]);
printf("%d\n",ans);
//cout<<dp[2]<<endl;
}
return 0;



0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有