Full Path Eraser Solution Codechef

Full Path Eraser Solution Codechef

There is a rooted tree of N vertices rooted at vertex 1. Each vertex v has a value Av​ associated with it.

You choose a vertex v (possibly the root) from the tree and remove all vertices on the path from the root to the vertex v, also including v. This will result in a forest of zero or more connected components.

The beauty of a connected component is the GCD of the values of all vertices in the component. Find the maximum value of the sum of beauties of the obtained connected components for any choice of v.

Here, GCD stands for Greatest Common Divisor.

Input Format

  • The first line contains a single integer T — the number of test cases. Then the test cases follow.
  • The first line of each test case contains an integer N — the size of the tree.
  • The second line of each test case contains N space-separated integers A1​,A2​,…,AN​ denoting the values associated with each vertex.
  • The next N-1 lines contain two space-separated integers u and v — denoting an undirected edge between nodes u and v.

It is guaranteed that the edges given in the input form a tree.

Output Format

For each test case output the maximum value of the sum of beauties of the obtained connected components for any choice of v.

Constraints

  • 1≤T≤2⋅104
  • 1≤N≤3⋅105
  • 1≤Ai≤109
  • 1≤u,vN and uv
  • It is guaranteed that the edges given in the input form a tree.
  • The sum of N over all test cases does not exceed 3⋅105

Sample 1:

Input

1
10
15 30 15 5 3 15 3 3 5 5
1 2
1 5
2 3
2 4
5 6
5 7
5 8
7 9
7 10

Output

33

Explanation:

The tree from the sample is as follows.

![tree_basic]

Full Path Eraser Solution Codechef
Tree Basic

If vertex v = 7 is chosen, vertices 1, 5 and 7 are removed.

![tree_remove]

Full Path Eraser Solution Codechef
Tree Remove

The resulting forest contains five connected components {8},{6},{10},{9} and {2,3,4}.

![tree_value]

Full Path Eraser Solution Codechef
Tree Value

The beauties of the connected components are 33, 1515, 55, 55 and 55 respectively. Thus the answer is 3 + 15 + 5 + 5 + 5 = 33.

It can be shown that this is the maximum value possible for any choice of v.

SOLUTION

Program: Full Path Eraser Solution in Python

import sys
from math import gcd
sys.setrecursionlimit(1000000)

def mi():
    return map(int, input().split())

def li():
    return list(mi())

def si():
    return str(input())

def ni():
    return int(input())

def findgcd(g, nodegcd, node, a, visited):

    ans = a[node - 1]

    for i in g[node]:
        if i not in visited:
            visited.add(i)
            ans = gcd(findgcd(g, nodegcd, i, a, visited), ans)

    nodegcd[node] = ans
    return ans

def findpath(g, path, node, visited, curr, nodegcd):
    for i in g[node]:
        if i not in visited:
            visited.add(i)

            ans = int(curr)
            ans -= nodegcd[i]

            for j in g[i]:
                if j not in visited:
                    ans += nodegcd[j]
            path[i] = ans
            findpath(g, path, i, visited, ans, nodegcd)

for t in range(int(input())):

    n = ni()
    a = li()
    g = []
    for i in range(n + 1):
        g.append([])

    for i in range(n - 1):
        x, y = mi()
        g[x].append(y)
        g[y].append(x)

    nodegcd = dict()
    findgcd(g, nodegcd, 1, a, {1})
    path = dict()
    path[1] = 0
    for i in g[1]:
        path[1] += nodegcd[i]
    findpath(g, path, 1, {1}, path[1], nodegcd)
    print(max(path.values()))

Program: Full Path Eraser Solution in C++

#include<bits/stdc++.h>
using namespace std;
#define int long long int
 
int n=3e5+5;
int ans=0;
vector<vector<int>>adj(n);
vector<int>a(n),sub(n);

void dfs(int u, int p){
    sub[u]=a[u];
    for(auto &v: adj[u]){
        if(v==p){continue;}

        dfs(v,u);
        sub[u]=__gcd(sub[u],sub[v]);
    }
}
void dp(int u, int p, int above){
    int sum=0;
    for(auto &v: adj[u]){
        if(v==p){continue;}
        sum+=sub[v];
    }
    ans=max(ans,sum+above);

    for(auto &b: adj[u]){
        if(b==p){continue;}
        dp(b,u,sum+above-sub[b]);
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t; cin>>t;
    while(t--){
      cin>>n; ans=0;
      for(int i=1; i<=n; i++){
        cin>>a[i],adj[i].clear();
      }
      for(int i=1; i<n; i++){
        int a,b; cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
      }
      dfs(1,-1);
      dp(1,-1,0);
      cout<<ans<<"\n";
    }
     
    return 0;
}

Program: Full Path Eraser Solution in Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Codechef{
    public static void main(String[] args) throws Exception{
        BufferedReader bu = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String[] s = bu.readLine().split(" ");
        int tt = Integer.parseInt(s[0]);
        for(int t=0; t<tt; ++t) {
            s = bu.readLine().split(" ");
            int n = Integer.parseInt(s[0]);
            int[] a =new int[n];
            s = bu.readLine().split(" ");
            for(int i=0; i<n; ++i) a[i] = Integer.parseInt(s[i]);
            ArrayList<Integer>[] g = new ArrayList[n];
            for(int i=0; i<n; ++i) g[i] = new ArrayList<>();
            for(int i=1; i<n; ++i) {
                s = bu.readLine().split(" ");
                int u = Integer.parseInt(s[0]) - 1, v = Integer.parseInt(s[1]) - 1;
                g[u].add(v);
                g[v].add(u);
            }
            long[] sum = new long[n];
            int[] gcdOfSubtree = new int[n];
            calculateGCD(g,0,-1,a,sum,gcdOfSubtree);
            long[] ans = new long[1];
            dfs(g,0,-1,sum,gcdOfSubtree,ans,0);
            sb.append(ans[0]+"\n");
        }
        System.out.println(sb);
    }

    private static void dfs(ArrayList<Integer>[] g, int n, int p, long[] sum, int[] gcdOfSubtree, long[] ans, long sumTillNow) {

        ans[0] = Math.max(ans[0],sumTillNow+gcdOfSubtree[n]);

        for(int c: g[n]) if(c!=p)
            dfs(g,c,n,sum,gcdOfSubtree,ans,sumTillNow+sum[n]-gcdOfSubtree[c]);
    }

    private static void calculateGCD(ArrayList<Integer>[] g, int n, int p, int[] a, long[] sum, int[] gcdOfSubtree) {
        gcdOfSubtree[n] = a[n];
        for(int c: g[n]) if(c!=p){
            calculateGCD(g,c,n,a,sum,gcdOfSubtree);
            gcdOfSubtree[n] = gcd(gcdOfSubtree[n],gcdOfSubtree[c]);
            sum[n] += gcdOfSubtree[c];
        }
    }

    private static int gcd(int a, int b) {
        return b==0?a:gcd(b,a%b);
    }
}

Related:

Leave a Comment

3 × 4 =