Блог пользователя ShashwatS1

HELP Weighted Tree — tree problem
Автор ShashwatS1, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

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

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;
}
→ Ответить