Join Us
Loading Similar Posts
Entering edit mode
A tree is represented as an undirected connected graph of n nodes numbered from 1 to n and n- 1 edges. The ith edge connects the nodes numbered from edges[i][0] and edges[i][1] and each node i is associated with a value val[i],
In a special move, any node can be visited from any other node directly via teleportation.
Given val and edges, find the maximum sum of values of the nodes visited on a path starting and ending at node number 1 by using the special move at most once and visiting any edge at most once.
Example
Suppose n = 3, val = [10, 20, 30], edges = [[1, 2], [1, 3]]
The Optimal path is so to traverse from node 1 to 3 and then use the special move to reach 2 and then back again to 1.
Function Description
Complete the function getMaxValueSum in the editor below.
getMaxValueSum takes two parameters:
int val[n]: the values associated with the nodes
int edges[n-1][2]: the edges of the tree
Returns
long int. the maximum sum of values of the nodes visited
Constraints
• 1 ≤ n ≤ 105
• 1 ≤ val[i] ≤109 
Sample Input For Custom Testing
STDIN FUNCTION
5. val [] size n = 5
1 val = [1, 2, 3, 4, 5]
2
3
4
5
4 edges [] size n - 1 = 4
2 edges [][] size const = 2
1 2 edges = [[1, 2], [1, 3], [2, 4], [2, 5]]
1 3
2 4
2 5
Sample Output
11
Explanation
The optimal path is to move from 1 to 3 and then use the special move to reach 5. From 5 move to 2 and then back to 1. The nodes visited are 1,2,3,5 with sum of values 1+2+3+5=11.
Entering edit mode
PROBLEM 1:
Probable solution:- https://ideone.com/SJXIlw
Entering edit mode
#include<bits/stdc++.h>
using namespace std;
//for pbds(order set)
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// // find_by_order(index pr kayu element che), order_of_key(how many lesser element)
// --------------------------------------
#define hiii ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
#define ld long double
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pb push_back
#define pp pop_back
#define sort(v) sort((v).begin(),(v).end())
// -------------------------------------
int ans=0;
vector<int> vis;
vector<int> v;
int f(int s,vector<vector<int>> &adj,int par){
if(vis[s] && s==1)return 0;
if(vis[s])return -1e7;
vis[s]=1;
//cout<<s<<endl;
int t=0;
for(auto &i:adj[s]){
if(i==par)continue;
t=max(t,v[s]+f(i,adj,s));
}
vis[s]=0;
return t;
}
int main(){
ll n,m;
cin>>n>>m;
v.resize(n+1);
for(int i=1;i<=n;i++){
cin>>v[i];
}
vector<vector<int>> adj(n+1);
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1;i<=n;i++){
adj[0].push_back(i);
adj[i].push_back(0);
}
vis.resize(n+1,0);
ans=f(1,adj,0);
cout<<ans<<endl;
}
