5 months ago

PoGo 2.5k

Hyderabad

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 ≤ 10⁵ 

• 1 ≤ val[i] ≤10⁹ 

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.

5 months ago

PoGo 2.5k

Hyderabad

PROBLEM 1:

Probable solution:- https://ideone.com/SJXIlw

14 months ago

Krishna • 30

Lucknow

#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;

}