ITREE - Nhãn của cây
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
const int N = 1010;
using namespace std;
vector<int> a[N];
int w[N];
int t, n;
int DP(int u) {
if (a[u].size() == 0) return 0;
int tmp = 0;
for(int i = 0; i < a[u].size(); i++)
tmp += DP(a[u][i]);
if (u != 1) return min(0, tmp + w[u]);
else return tmp + w[u];
}
int main() {
scanf("%d", &t);
int u, uv;
while (t--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{a[i].clear(); w[i] = 0;}
for(int v = 2; v <= n; v++) {
scanf("%d %d", &u, &uv);
a[u].push_back(v);
w[u] += uv; w[v] -= uv;
}
printf("%d.00\n", DP(1));
}
return 0;
}