Codeforces 1637 F. Towers - thinking, DFS

This way

The question ：

Give you a tree , Each point has a value a[i]. You have to put value on some points b[i], So that for any point x, There are two points u,v：x stay u,v And min(b[u],b[v])>=a[x].
Ask you the least b What is the sum .

Answer key ：

I put ne It has been written. x, For half an hour bug.
We just need to put a The largest point is the root rt, And then for any one x(x!=rt), Only one of its subtrees is needed b>=a[x] that will do .
Because in the end we need the value of two points >=a[rt], So for any one x(x!=rt) Come on , There must be at least one point not in its subtree .
We record mx[x] Represents the current subtree b The maximum of ,smx Means different from mx The maximum value in other subtrees of .
If the current is the root , Then we need two points to support him , Otherwise, only one point is needed .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
vector<int>vec[N];
int a[N],mx[N],smx[N],rt;
ll ans;
void dfs(int x,int fa){
    
    if(x-rt&&vec[x].size()==1)mx[x]=a[x],ans+=a[x];
    for(int ne:vec[x]){
    
        if(ne==fa)continue;
        dfs(ne,x);
        if(mx[ne]>mx[x])smx[x]=mx[x],mx[x]=mx[ne];
        else if(mx[ne]>smx[x])smx[x]=mx[ne];
    }
    if(x-rt){
    
        if(mx[x]<a[x])
            ans+=a[x]-mx[x],mx[x]=a[x];
    }
    else{
    
        if(!smx[x])ans+=a[x]+a[x]-mx[x];
        else ans+=a[x]*2-mx[x]-smx[x];
    }
}
int main()
{
    
    int n,x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),rt=a[rt]>=a[i]?rt:i;
    for(int i=1;i<n;i++)
        scanf("%d%d",&x,&y),vec[x].push_back(y),vec[y].push_back(x);
    dfs(rt,0);
    printf("%lld\n",ans);
    return 0;
}