Need help in SPOJ Problem

I am trying to solve this problem on SPOJ. But I am clueless, how should i proceed? Essentially, we need to find longest path in given undirected weighted graph using dfs perhaps from every node and maybe use dynamic programming,but how to do that? Please help.

I would appreciate it.

Let’s root the tree at 1.

Let dp_u be the largest path from u to a leaf in the subtree of u. We can see that dp_u = max(dp_v + w), where v is adjacent to u and w is the weight of the edge between u and v. This way we can calculate the answer for node 1.

Let’s say some node v is adjacent to u with a weight w. We can reroot our tree from u to v.

To do that, we must first let dp_u as the set of all possible values of dp_v + w.

Now we can remove \max(dp_v) + w from dp_u, and then add \max(dp_u) + w to dp_u.

Now we have successfully calculated the answer for v, which is \max(dp_v).

Now we must reroot our trees over all nodes.
To get this path, Let’s define f(i) as a path that starts at i, and then goes over all nodes in the subtree of i and ends at i. We can notice that
f(i) = \sum\limits_{v\in adj_u}(i + f(v)) + i
Fun fact : This is exactly how a DFS moves around the graph.
You can trace the new DFS to reroot the tree, or memorise the path.

Code with 2 DFS
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
void solve(){
    int n;
    cin>>n;
    vector<vector<pair<int,int>>> adj(n);
    for(int i=0;i<n-1;i++){
        int u,v,w;
        cin>>u>>v>>w;
        --u;--v;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    vector<multiset<ll>> dp(n, {0});
    vector<pair<int,int>> path;
    path.reserve(n<<1);
    path.pb({0,0}); 
    function<void(int,int)> dp1 = [&](int u,int par){
        for(const auto& x : adj[u]){
            const auto &v = x.first, &w = x.second; 
            if(v == par){
                continue;
            }
            dp1(v, u);
            dp[u].insert(*(--dp[v].end()) + w);
        }
    };
    dp1(0,0);
    vector<ll> ans(n);
    function<void(int,int)> dp2 = [&](int u,int par){
        ans[u] = *(--dp[u].end());
        for(const auto& x : adj[u]){
            const auto &v = x.first, &w = x.second; 
            if(v == par){
                continue;
            }
            dp[u].erase(dp[u].find(*(--dp[v].end()) + w));
            dp[v].insert(*(--dp[u].end()) + w);
            dp2(v, u);
            dp[v].erase(dp[v].find(*(--dp[u].end()) + w));
            dp[u].insert(*(--dp[v].end()) + w);
        }
    };
    dp2(0,0);
    for(const auto &x : ans){
        cout<<x<<" ";
    }
    cout<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}
Code with path memorisation
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
void solve(){
    int n;
    cin>>n;
    vector<vector<pair<int,int>>> adj(n);
    for(int i=0;i<n-1;i++){
        int u,v,w;
        cin>>u>>v>>w;
        --u;--v;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    vector<multiset<ll>> dp(n, {0});
    vector<pair<int,int>> path;
    path.reserve(n<<1);
    path.pb({0,0}); 
    function<void(int,int)> solve = [&](int u,int par){
        for(const auto& x : adj[u]){
            const auto &v = x.first, &w = x.second; 
            if(v == par){
                continue;
            }
            path.pb({v,w});
            solve(v, u);
            path.pb({u,w});
            dp[u].insert(*(--dp[v].end()) + w);
        }
    };
    solve(0,0);
    vector<ll> ans(n);
    for(int i=1;i<path.size();i++){
        const auto& u = path[i-1], v = path[i];
        dp[u.first].erase(dp[u.first].find(*(--dp[v.first].end()) + v.second));
        dp[v.first].insert(*(--dp[u.first].end()) + v.second);
        ans[v.first] = *(--dp[v.first].end());
    }
    for(const auto &x : ans){
        cout<<x<<" ";
    }
    cout<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}
1 Like

Hey, thanks for the reply. Can you please explain in little more detail from this line onwards:

“Now we can remove \max(dp_v) + w from dp_u, and then add \max(dp_u) + w to dp_u.”

EDIT: After analysing the codes, I understood what and why we are doing. Thanks a lot for your help.