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.
#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();
}
}
#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();
}
}
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.