5.cpp

来自「一次比赛的代码,有五道题,2,4比较基础,3题是模拟,1高精度,5树状dp」· C++ 代码 · 共 53 行

#include <iostream>
using namespace std;
int max(int a,int b)
{ 
	if(a>b)
		return a;
	else return b;
}
int n;
int Max=0;
bool  map[1600][1600];//储存点与点的连通情况
int p[1600];	      //存放点的权值
int dp(int mf,int mn)//mf到点mn
{
        int re=p[mn];
        for(int i=0 ; i < n ; i++)
        {
			if(map[mn][i] == 1)
			{int next = i;
            if(mf==next)  continue;
            int dp_now = dp(mn,next);
            if(dp_now>0)
                re += dp_now;
		}
}
		Max=max(Max, re);//取最大值 ；
        return re;
    }
 void main() 
{
	freopen("cut.in","r",stdin);
	freopen("cut.out","w",stdout);
	memset(map,0,sizeof(map));
	cin>>n;
	for( int i = 0 ; i < n; i ++)//读入点的权值
	{	int temp;
		cin>>temp;
		p[i] = temp;
	}
	for( i=0;i<n-1;i++)//读入点与点的连通情况；
	{
			int x,y;
			cin>>x>>y;
			map[x-1][y-1] = 1;
			map[y-1][x-1] = 1 ;
	}
      dp(0,1);//dp搜图；
      cout<<Max<<endl;//输出最大
}