CodeForces 1084D The Fair Nut and the Best Path

时间：2021-12-14 05:52:14

The Fair Nut and the Best Path

题意：求路径上的 点权和 - 边权和 最大， 然后不能存在某个点为负数。

题解：

dfs一遍， 求所有儿子走到这个点的最大值和次大值。

我们需要明白如果可以从u -> v  那么一定可以从 v -> u， 当然 指的是 u->v是路径上的最大和。

u->e1->v;

假如:val[u] = 100, val[e1] = 50, val[v] = 60, 那么我们发现可以从 u -> v 也可以从v -> u

val[u] = 100, val[e1] = 50, val[v] = 40, 虽然我们可以从u->v，但是 不能 v->u， 但是根据上面的定义，我们发现 从 u->v反而是亏本的，也就是说 u->u是最大的，我们不在考虑 u->v了。

val[u] = 40, val[e1] = 50, val[v] = 100, 和上面一样的道理。

所以，当一条路是最大的能赚的话， 那么一定可以走双向。

然后 现在还有一个疑问就是  如果从 u的父节点到u呢， 这个东西在 u往上传的时候就解决了。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 3e5 + ;

const int M = *N;

int head[N], to[M], val[M], nt[M], tot;

void add(int u, int v, int w){

    to[tot] = v;

    val[tot] = w;

    nt[tot] = head[u];

    head[u] = tot++;

}

LL dp[N][];

int a[N];

LL ans = ;

LL dfs(int o, int u){

    for(int i = head[u]; ~i; i = nt[i]){

        int v = to[i];

        if(v == o) continue;

        LL tmp = dfs(u,v) - val[i];

        if(tmp > dp[u][]) swap(tmp, dp[u][]);

        if(tmp > dp[u][]) swap(tmp, dp[u][]);

    }

    ans = max(ans, dp[u][]+dp[u][]+a[u]);

    return dp[u][] + a[u];

}

int main(){

    int n, u, v, w;

    scanf("%d", &n);

    memset(head, -, sizeof(head));

    for(int i = ; i <= n; ++i) scanf("%d", &a[i]);

    for(int i = ; i < n; ++i){

        scanf("%d%d%d", &u, &v, &w);

        add(u,v,w);

        add(v,u,w);

    }

    dfs(,);

    cout << ans << endl;

    return ;

}

相关文章