CCA的搬运
CCA的搬运
https://ac.nowcoder.com/acm/problem/217041
题目大意：
选两个节点u,v，使得两个节点的子树和权值最大，且fa[u]!=fa[v]
思路：
对于一个节点u假设有子节点v1,v2,v3.....
我们用mx[u] 记录u的子节点及其孙子节点中（反正就是u点下面的）任意一点为根的子树和最大值；
有没有大佬帮我用术语描述一下上面的句子
sum[u]为以u为根的子树和
N^2枚举两个点显然是不行的
缩小答案产生的范围
对于一个节点u
那么答案肯定产生于他两侧的所有节点中
我们mx记录的这个东西刚好记录了一个节点下面所有的节点
所以我们选出一个最大，一个次大就行了
CODE：
int head[maxn],cnt;
struct node {
int u,v,w,next;
} e[maxn];
void add(int u,int v) {
e[cnt].u=u,e[cnt].v=v;
e[cnt].next=head[u],head[u]=cnt++;
}
ll n,val[maxn],fa[maxn],sum[maxn],ans = -1e17,ma[maxn];
void dfs(int u,int p) {
fa[u] = p, sum[u] =val[u];
for(int i=head[u]; ~i; i=e[i].next) {
int v = e[i].v;
if(***bsp;continue;
dfs(v,u);
sum[u]+=sum[v];
}
ma[u] = sum[u];
for(int i=head[u]; ~i; i=e[i].next) {
int v = e[i].v;
if(***bsp;continue;
ma[u] = max(ma[u],ma[v]);
}
}
void dfs2(int u,int p) {
ll ma1 = -1e17;
ll ma2 = -1e17;
for(int i=head[u]; ~i; i=e[i].next) {
int v = e[i].v;
if(***bsp;continue;
if(ma[v]>=ma1) {
ma2 = ma1;
ma1 = ma[v];
} else if(ma[v]>ma2) {
ma2 = ma[v];
}
dfs2(v,u);
}
if(ma2!=-1e17)
ans = max(ans,ma1+ma2);
}
int main() {
mst(head,-1);
n=read();
rep(i,1,n) val[i] = read(),ma[i] = -1e17;
for(int i=1 ; i<n ; i++) {
ll u,v;
u=read(),v=read();
add(u,v),add(v,u);
}
dfs(1,1);
dfs2(1,1);
if(ans!=-1e17) out(ans);
else puts("Error");
return 0;
}
/*
*/ 
投递荣耀等公司9个岗位 >
