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);
};
};