AcWing 1220. 生命之树
原题链接
中等
作者:
猪啊猪
,
2021-12-21 23:02:12
,
所有人可见
,
阅读 223
菜鸡题解 三遍才ac,,这要是IO赛制也看不出来啊。。
第一反应:题型以及相似题:树型dp 树的深度遍历 树的重心 s
难点1:读题 本题说序列中的两点存在一条”边”,我误以为是一条直接相连的边,后来反应过来是指一条路径
呆比点2:树的深度遍历。。记得把自己当前点标记为true,找了好半天才找出来,太生疏了。。。
易错点3:一定要把当前走到的dfs的点的w[u]加上,即当前点必须走,只有这样他才有资格把他的出边连接在一起
易错点4:long long 以及 ans的初始化
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 100010,INF = 0x3f3f3f3f;
typedef long long LL;
int e[maxn*2];
int ne[maxn*2];
int h[maxn];
int w[maxn];
int idx;
bool st[maxn];
LL ans = -INF;
void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
LL dfs(int u) // 返回以u为根的连通块的最大值 , 即w[u]一定走
{
// cout<<u<<endl;
st[u] = true; // 记得把自己标记成true!!!!
LL res = w[u];
for(int i=h[u];i!=-1;i=ne[i]) // u的所有出边
{
int j = e[i];
if(!st[j])
{
st[j] = true;
res += max(dfs(j),(LL)0); // 0 即那个分支不算。
}
}
ans = max(ans,res); // 以当前为根的最大连通块值
return res;
}
int main()
{
memset(h,-1,sizeof h);
int n;
cin>>n;
for(int i=1;i<=n;++i) cin>>w[i];
for(int i=1;i<=n-1;++i)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(1);
cout<<ans<<endl;
}