Tree Decoration

For example, consider the tree below where nodes located higher on the display are parents of connected lower nodes (1 is the root): 1 | 2 | 5 / \ 4 3 Suppose that FJ has the following subtree constraints: Minimum ornaments the subtree requires | Time to install an ornament Subtree | | root | C_i | T_i --------+--------+------- 1 | 9 | 3 2 | 2 | 2 3 | 3 | 2 4 | 1 | 4 5 | 3 | 3 Then FJ can place all the ornaments as shown below, for a total cost of 20: 1 [0/9(0)] legend: element# [ornaments here/ | total ornaments in subtree(node install time)] 2 [3/9(6)] | 5 [0/6(0)] / \ [1/1(4)] 4 3 [5/5(10)]

C++(g++ 7.5.0) 解法, 执行用时: 59ms, 内存消耗: 7004K, 提交时间: 2023-02-10 20:31:58

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

constexpr int N=1e5+5;
vector<ll> g[N];
ll w[N],l[N],sz[N];
ll dfs(ll u)
{
    ll res=0;
    for(ll v:g[u])
    {
        res+=dfs(v);
        w[u]=min(w[u],w[v]);
        sz[u]+=sz[v];
    }
    if(sz[u]<l[u]) res+=(l[u]-sz[u])*w[u],sz[u]=l[u];
    return res;
}

int main()
{
    ios::sync_with_stdio(0);
    ll n;
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        ll v;
        cin>>v>>l[i]>>w[i];
        if(v==-1) continue;
        g[v].push_back(i);
    }
    cout<<dfs(1);
    return 0;
}

Python3 解法, 执行用时: 618ms, 内存消耗: 25028K, 提交时间: 2023-05-25 14:00:06

import collections
n = int(input())
c = [0]*(n+1)
t = [0]*(n+1)
mm = [99999]*(n+1)
edge = [[] for _ in range(n+1)]
cost = [0]*(n+1)
s = [0]*(n+1)
res = 0


for i in range(1, n+1):
    p, a, b = map(int, input().split())
    c[i] = a
    t[i] = b
    if p==-1:
        continue
    edge[p].append(i)
    

def dfs(i):
    mm[i] = t[i]
    for j in edge[i]:
        dfs(j)
        mm[i] = min(mm[i], mm[j])
        s[i] += s[j]
    if c[i]>s[i]:
        global res
        res += mm[i]*(c[i]-s[i])
        s[i] = c[i]

dfs(1)

print(res)

C++(clang++11) 解法, 执行用时: 50ms, 内存消耗: 5880K, 提交时间: 2021-03-16 16:48:27

#include<bits/stdc++.h>
using namespace std;

long long ans=0,S[100005]={0};
int i,j,n,c[100005],t[100005];
vector<int>R[100005];
void DFS(int x)
{
	int i,j;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		DFS(j),t[x]=min(t[x],t[j]),S[x]+=S[j];
	}
	if(S[x]<c[x])ans+=t[x]*(c[x]-S[x]),S[x]=c[x];
}
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
    	scanf("%d%d%d",&j,&c[i],&t[i]);
    	if(j!=-1)R[j].push_back(i);
	}
	DFS(1);
	printf("%lld\n",ans); 
    return 0;
}

详情