Max absolute path sum in a tree with atmost k inversions.

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:23:50
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

--n--'s blog

Max absolute path sum in a tree with atmost k inversions.

By --n--, history, 4 years ago, In English

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.

--n--
4 years ago
11

Comments (3)

Show archived | Write comment?

Living_Tribunal

4 years ago, # |

← Rev. 2 →

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<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(long i=a;i<b;i++)
#define pb push_back
#define ll long long
#define pob pop_back
#define si second
#define fi first
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) 
 
int dp[1000][1000];
vector<pair<int,int>> adj[1000];
int n,K;

int dfs(int node,int pa,int k){

//cout<<node<<" "<<pa<<" "<<k<<" "<<dp[node][k]<<"\n";
if(dp[node][k]!=-1){ return dp[node][k];}


int ans=-99999999; int ch=0;
	for(auto u:adj[node]){ 
	if(u.fi!=pa){ ch++;
		if(k<K){ 
		int d1=u.si+dfs(u.fi,node,k); //cout<<d1<<" d1 "<<u.fi<<" "<<node<<"\n";
		int d2=-u.si+dfs(u.fi,node,k+1); //cout<<d2<<" d2 "<<u.fi<<" "<<node<<"\n";
		ans=max(ans,max(d1,d2  ));}
		else{ ans=max(ans,u.si+dfs(u.fi,node,k)); //cout<<ans<<" a "<<u.fi<<" "<<node<<"\n"; 
		}
	}

	}
if(ch==0){ ans=0;}
dp[node][k]=ans;
//cout<<"dp "<<dp[node][k]<<"\n";
return ans;
}

//================================================//

int main(){
fastio;
 cin>>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<<ans<<"\n";

return 0;}

Some testcases and ans

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

→ Reply

navneet.h

4 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

akshat_porwal

3 years ago, # |

Can anyone tell what should the dp states be and the corresponding recurrence relation?

→ Reply