### --n--'s blog

By --n--, history, 8 days ago,

Please help me solving this problem. I am not getting any idea how to proceed.

You are given an undirected weighed tree with N node . You need to find maximum absolute path sum in the tree with atmost k inversions. In one inversion you can change the weight of an edge from negative to positive and vice versa.

• +1

 » 8 days ago, # |   0 Auto comment: topic has been updated by --n-- (previous revision, new revision, compare).
 » 8 days ago, # |   0 I think state would be like this : dp[i][j] is the maximum path sum if we are at some node i and have already seen j inversions. Maybe Tree Dp will help.
 » 8 days ago, # |   0 Can you please give the link of problem?
 » 8 days ago, # | ← Rev. 2 →   0 I solved it in O(n^3), n^2 dp considering one node as root, and O(n^3) by considering every node as root and choosing maximum from them, My O(n^3) code#include using namespace std; #define FOR(i,a,b) for(long i=a;i> adj[1000]; int n,K; int dfs(int node,int pa,int k){ //cout<>n>>K; int a,b,k; FOR(i,0,n-1){ cin>>a>>b>>k; adj[a].pb({b,k}); adj[b].pb({a,k}); } int ans=-99999999; FOR(i,1,n+1){ memset(dp,-1,sizeof(dp)); ans=max(ans,dfs(i,-1,0)); } cout<16 6 1 1 2 2 2 5 -1 2 6 -3 1 4 -5 4 3 6 ans->13 But i believe n^2 solution is possible with rerooting DP, i tried that also but I'm somewhat confused in one concept of it
•  » » 7 days ago, # ^ | ← Rev. 2 →   0 no need for rerooting just maintain root to the certain node using $X$ inversions max possible answer similarly do for children and then chose appropriately. either it could be child-child or child-ancestor for best path sum.
•  » » » 7 days ago, # ^ |   0 Hey navneet thanks but can you explain more with example if possible
•  » » 3 days ago, # ^ |   0 bro we need to find maximum absolute path sum
•  » » » 3 days ago, # ^ |   0 I think that's what i wrote , the solution is just one abs() function call away
 » 5 days ago, # |   0 Can you provide link for the question of this problem