ShashwatS1's blog

HELP Weighted Tree — tree problem
By ShashwatS1, history, 6 years ago, In English

Given a tree T containing N nodes numbered [1,2..,N] rooted at node 1 . Each edge has a value associated with it.You are also given a number K. You need to find the maximum weight you can collect in K-steps .When you traverse an edge, it is counted as 1 step.

Note:
1. you should start from root node.
2. you can traverse an edge from parent to child or child to parent.
3. you can traverse an edge multiple times.
4. weights of edges are always positive integer.

Constraints:
0<=K<=1000000
0<=N<=500000
0<=weights<=1000000000

Input format:

  1. first line contain N,K i.e number of nodes, number of steps respectively.
  2. next N-1 lines contain three integers a,b,c i.e there is an edge between 'a' and 'b' with weight 'c'.

Output format:

maximum weight collected in K-steps.

Example:-
Input:
6 3
1 2 5
1 3 6
2 4 15
2 5 1
3 6 11

Output: 35

Explanation:

Traversal for max. weight collection: [1-2-4-2]. Thus weight collected 5+15+15=35

How to solve this question? Plz Help. Thanks in advance.

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Any link, please! and are you sure it is tree? why then to input M? Trees have N-1 edges always, where N is the number of nodes in it.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Actually this is an private contest question so link isn't available now. I updated the statement. Sorry for mistake.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are bounds?

We can solve easily in N*K time by making a dp table for [steps taken][node] and filling it layer by layer by walking through the edges each time and maximizing c + [k-1][a] into [k][b] and verse visa.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We can also solve this in n time by recognizing that it's always best to do all of our switchbacks on the largest edge we visit. That edge must be the last one for an optimal solution. Therefore we can just do a dfs and keep how many moves are left as well as the path weight. Each node then yields one possible solution which uses its parent edge for all the remaining moves. Take the max.

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

The answer is always going down from root to some node v and then traversing the edge connecting v with its parent for the remaining steps.

Start a dfs from root and try every possible node v, and take the maximum.

UPD: never mind :3

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

check my solution

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

int n,k;

vector<pair<int,ll>> tree[500001];

int vis[500001];

ll ans;

void solve(int x, ll sum, ll chance)
{
    vis[x] = 1;
    
    if(chance <= 0)
    {
        return;
    }
    
    for(int i = 0; i < tree[x].size(); i++)
    {
        pair<int,ll> p;
        
        p = tree[x][i];
        
        if(vis[p.first] == 0)
        {
            ll temp = sum + (p.second * chance);
            
            if(temp > ans)
                ans = temp;
                
            sum = sum + p.second;
            
            solve(p.first, sum, chance-1);
            
            sum = sum - p.second;
        }
    }
    
}
int main()
{
    cin >> n >> k;
    
    for(int i = 0; i < n-1; i++)
    {
        ll a,b,c;
        
        cin >> a >> b >> c;
        
        pair<int,ll> p;
        
        p = make_pair(a,c);
        
        tree[b].push_back(p);
        
        p = make_pair(b,c);
        
        tree[a].push_back(p);
    }
    
    ans = 0;
    memset(vis,0,sizeof(vis));
    
    solve(1, 0, k);
    
    cout << ans;
}
→ Reply