ITREE - Nhãn của cây

Tác giả: ll931110

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MAX 1000000000
typedef long long ll;
using namespace std;

int n;
int f[1010][2];
vector< pair<int,int> > adj[1010];

void DFS(int u)
{
     if (adj[u].empty())
     {
        f[u][0] = 0;  f[u][1] = MAX;  return;
     };
     for (int i = 0; i < adj[u].size(); i++) DFS(adj[u][i].first);
     f[u][0] = 0;  f[u][1] = 0;
     for (int i = 0; i < adj[u].size(); i++) 
     {
         f[u][0] += f[adj[u][i].first][0];
         f[u][1] += min(f[adj[u][i].first][1],f[adj[u][i].first][0] + adj[u][i].second);
     };
};

int main()
{
//    freopen("itree.in","r",stdin);
//    freopen("itree.ou","w",stdout);
    int T;
    scanf("%d", &T);
    while (T--)
    {
          scanf("%d", &n);
          for (int i = 1; i<= n; i++) adj[i].clear();
          for (int i = 2; i <= n; i++)
          {
              int pre,val;
              scanf("%d %d", &pre, &val);
              adj[pre].push_back(make_pair(i,val));
          };
          DFS(1);
          double ret = f[1][1] * 1.0;
          printf("%.2lf\n", ret);
    };
};

Download