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,v≤N and u≠v
- 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]
If vertex v = 7 is chosen, vertices 1, 5 and 7 are removed.
![tree_remove]
The resulting forest contains five connected components {8},{6},{10},{9} and {2,3,4}.
![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:
