Cerinta completa

Recall that a tree is an undirected, connected acyclic graph. We have a weighted tree, , with vertices; let be the total sum of edge weights on the path between nodes and .

Let’s consider all the matrices, , such that:

  • for each and

We consider the total value of matrix to be:

Calculate and print the maximum total value of for a given tree, .

Input Format

The first line contains a single positive integer, , denoting the number of vertices in tree .
Each line of the subsequent lines contains three space-separated positive integers denoting the respective , , and values defining an edge connecting nodes and (where ) with edge weight .

Constraints

  • Test cases with have of total score
  • Test cases with have of total score

Output Format

Print a single integer denoting the maximum total value of matrix satisfying the properties specified in the Problem Statement above.

Sample Input

3
1 2 2
1 3 1

Sample Output

3

Explanation

In the sample case, matrix is:

The sum of the elements of the first row is equal to .

Limbajul de programare folosit: cpp14

Cod:

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <cmath>
#include <ctime>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector< vector<int> > vvi;
typedef vector<ll> vl;
typedef vector< vector<ll> > vvl;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define forv(i, v) forn(i, v.size())
#define all(v) v.begin(), v.end()
#define mp make_pair
#define pb push_back

struct Edge {
    int v, w;
    Edge() {}
    Edge(int v, int w) : v(v), w(w) {}
};

vector< vector<Edge> > g;
vl d;

void dfs(int v, int p) {
    for (Edge& e : g[v]) {
        if (e.v == p) continue;
        d[e.v] = d[v] + e.w;
        dfs(e.v, v);
    }
}

int main() {
#ifdef NEREVAR_PROJECT
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n; cin >> n;
    g = vector< vector<Edge> >(n);
    forn(i, n - 1) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--, b--;
        g[a].pb(Edge(b, c));
        g[b].pb(Edge(a, c));
    }
    d = vl(n, 0);
    dfs(0, -1);
    ll s0 = 0;
    forn(i, n) s0 += d[i];
    d = vl(n, 0);
    dfs(n - 1, -1);
    ll s1 = 0;
    forn(i, n) s1 += d[i];
    cout << min(s0, s1) << endl;
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464647309

Link challenge: https://www.hackerrank.com/challenges/tree-flow/problem

Tree Flow