# DLTNODE - Editorial

**URL:** <https://discuss.codechef.com/t/dltnode-editorial/96044>\
**Category:** editorial\
**Tags:** depth-first-search, easy, editorial, pre-computation, prefix-sum, trees, greatest-common-divisor, csns2021\
**Created:** [November 3, 2021, 3:08pm UTC](https://discuss.codechef.com/t/dltnode-editorial/96044 "2021-11-03T15:08:32Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![phantom654](https://discuss.codechef.com/user_avatar/discuss.codechef.com/phantom654/32/45991_2.png) [@phantom654](https://discuss.codechef.com/u/phantom654)\
**Post date:** [November 3, 2021, 3:08pm UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/1 "2021-11-03T15:08:32Z")

</div>

[Problem statement](https://www.codechef.com/CSNS21B/problems/DLTNODE)  
[Contest source](https://www.codechef.com/CSNS21B)

_ **Author, Editorialist :** _ [Dhananjay Raghuwanshi](https://www.codechef.com/users/dhananjay_777)  
_ **Tester :** _ [Miten Shah](https://www.codechef.com/users/mtnshh)

# DIFFICULTY:

Easy

# PREREQUISITES:

Tree Flattening, prefix sums, DFS and similar

# PROBLEM:

Given a tree consisting of N nodes. Each node is given some value. We have to delete one node from the tree such that the sum of GCD of node values in all connected components formed after deleting that node is as maximum as possible.

# EXPLANATION:

- One way is to delete each node one by one and check answer for each node and select maximum answer from them. But doing this lamely obviously will give TLE. So we will use tree flattening and prefix sum technique to do above task more optimally.
- First root the tree let at node 1 then flatten the tree by using tree flattening technique and along with it also store in and out time for each node and also store the GCD of each subtree and parent of each node by running a simple DFS from node 1. Now lastly precompute the GCD from both forward and backward side of the array obtained from tree flattening . Now we can easily calculate for each node the possible sum of GCD of node values in each connected component after removing that node, and can output maximum of them.

#### How to find answer for a particular node x

- To find answer for a node x, first let’s see what happens by deleting the node x. If we delete node x, then the total number of connected components formed will be Number of children of node x +1.
- Also for each child of node x we already have calculated the GCD of node values of all the node in subtree of it’s child as earlier we have precomputed GCD of each subtree. Now the part left is the part formed after removing the whole subtree of node x from the tree.
- To calculate GCD of all nodes values in this part we will make use of in and out time of node x and of prefix and suffix arrays of GCD’s we have earlier calculated.
- So this part is equal to the GCD(forward[in[x]-1],backward[out[x]+1]), the array forward[i] (prefix array) stores GCD of all the nodes from index 1 to i of the array obtained from tree flattening and backward[j] (suffix array) stores GCD of all the nodes from last index of array to index j of the array obtained from tree flattening.
- The answer for node x is equal to the sum all above parts we have calculated above.

# SOLUTION :

> **c++ Solution**
>
> ```auto
> #include <bits/stdc++.h>
> using namespace std;
> 
> #define int int long long
> #define fr(i, n) for (int i = 0; i < n; i++)
> #define fr1(i, n) for (int i = 1; i <= n; i++)
> #define S second
> #define F first
> #define pb(n) push_back(n)
> #define endl "\n"
> vector<int> v[1000001];
> int in[1000001] = {0};
> int out[1000001] = {0};
> int timer = 1, n, m, t, k, eq = 0;
> int flatentree[1000001];
> int parent[1000001];
> int gcd_subtree[1000001];
> int value[1000001];
> int gcd(int a, int b)
> {
> if (b == 0)
> return a;
> else
> return (gcd(b, a % b));
> }
> 
> int dfs(int x, int p)
> {
> parent[x] = p;
> flatentree[timer] = x;
> in[x] = timer++;
> gcd_subtree[x] = value[x];
> for (auto child : v[x])
> {
> if (child != p)
> {
> gcd_subtree[x] = gcd(dfs(child, x), gcd_subtree[x]);
> }
> }
> flatentree[timer] = x;
> out[x] = timer++;
> return (gcd_subtree[x]);
> }
> 
> signed main()
> {
> cin >> t;
> while (t--)
> {
> timer = 1;
> cin >> n;
> fr(i, n + 1)
> {
> v[i].clear();
> }
> 
> fr1(i, n - 1)
> {
> int a, b;
> cin >> a >> b;
> v[a].pb(b);
> v[b].pb(a);
> }
> fr1(i, n)
> {
> cin >> value[i];
> }
> dfs(1, -1);
> int si = 2 * n;
> int forward[si + 1], backward[si + 1];
> forward[1] = backward[si] = value[1];
> for (int i = 2; i <= si; i++)
> {
> forward[i] = gcd(forward[i - 1], value[flatentree[i]]);
> }
> for (int i = si - 1; i >= 1; i--)
> {
> backward[i] = gcd(backward[i + 1], value[flatentree[i]]);
> }
> int ans = 1;
> int temp;
> fr1(i, n)
> {
> vector<int> children;
> for (auto child : v[i])
> {
> if (child != parent[i])
> {
> children.pb(gcd_subtree[child]);
> }
> }
> if (children.size() != 0)
> {
> temp = 0;
> for (auto j : children)
> {
> temp += j;
> }
> int temp1;
> if (i != 1)
> {
> temp1 = gcd(forward[in[i] - 1], backward[out[i] + 1]);
> ans = max(ans, temp + temp1);
> }
> else
> {
> ans = max(ans, temp);
> }
> }
> else
> {
> temp = gcd(forward[in[i] - 1], backward[out[i] + 1]);
> ans = max(ans, temp);
> }
> }
> cout << ans << endl;
> }
> }
> 
> ```

[details=‘C++ Tester’s solution’]

```auto
// created by mtnshh

#include<bits/stdc++.h>
#include<sys/resource.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
  
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
 
#define err() cout<<"--------------------------"<<endl; 
#define errA(A) for(auto i:A) cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl

#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define ft first
#define sd second

#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
 
// #define endl "\n"

long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        // char g = getc(fp);
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
            
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
            // cerr << x << " " << l << " " << r << endl;
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        // char g=getc(fp);
        assert(g != -1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}

const int max_q = 1e3;
const int max_n = 1e5;
const int max_sum_n = 1e6;
const int max_ai = 1e9;

const ll N = 100005;
const ll INF = 1e12;

V adj[N];
ll A[N];

ll in[N], out[N], cnt = 0, pref[N], suff[N], ans = 0, ord[N];

void dfs1(ll n, ll p){
    in[n] = cnt;
    ord[cnt] = n;
    cnt += 1;
    for(auto i: adj[n]){
        if(i == p) continue;
        dfs1(i, n);
    }
    out[n] = cnt - 1;
}

ll dfs2(ll n, ll p){
    ll sum = 0, gcd = A[n];
    for(auto i: adj[n]){
        if(i == p) continue;
        ll q = dfs2(i, n);
        gcd = __gcd(gcd, q);
        sum += q;
    }
    sum += __gcd(pref[in[n]-1], suff[out[n]+1]);
    ans = max(ans, sum);
    return gcd;
}

void solve(ll n){
    rep(i,0,n+1) adj[i].clear();
    rep(i,0,n-1){
        ll u = readIntSp(1, n), v = readIntLn(1, n);
        adj[u].pb(v);
        adj[v].pb(u);
    }
    rep(i,1,n+1) A[i] = (i != n) ? readIntSp(1, max_ai) : readIntLn(1, max_ai);
    cnt = 1;
    dfs1(1, 0);
    pref[0] = 0;
    suff[n+1] = 0;
    rep(i,1,n+1){
        pref[i] = __gcd(pref[i-1], A[ord[i]]);
    }
    repb(i,n,1){
        suff[i] = __gcd(suff[i+1], A[ord[i]]);
    }
    ans = 0;
    dfs2(1, 0);
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll q = readIntLn(1, max_q);
    ll sum_n = 0;
    rlimit R;
    getrlimit(RLIMIT_STACK, &R);
    R.rlim_cur = R.rlim_max;
    setrlimit(RLIMIT_STACK, &R);
    while(q--){
        ll n = readIntLn(2, max_n);
        solve(n);
        sum_n += n;
    }
    assert(sum_n <= max_sum_n);
    assert(getchar()==-1);
}

```

[/details]

---

<div class="post-metadata">

**Author:** ![suri429](https://discuss.codechef.com/user_avatar/discuss.codechef.com/suri429/32/38405_2.png) [@suri429](https://discuss.codechef.com/u/suri429)\
**Post date:** [November 3, 2021, 6:42pm UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/2 "2021-11-03T18:42:14Z")

</div>

Hey, I used tree flattening and a sparse table to get gcd of a range. My code is getting SIGSEGV . Can I get to know a testcase ?  
[Solution](https://www.codechef.com/viewsolution/53437466)  
Thank you

---

<div class="post-metadata">

**Author:** ![bigbrain69](https://discuss.codechef.com/user_avatar/discuss.codechef.com/bigbrain69/32/24644_2.png) [@bigbrain69](https://discuss.codechef.com/u/bigbrain69)\
**Post date:** [November 3, 2021, 7:16pm UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/3 "2021-11-03T19:16:18Z")

</div>

Easy? Really?  
How do you guys rate problems? I don’t think this was an easy problem.

---

<div class="post-metadata">

**Author:** ![zexx](https://discuss.codechef.com/user_avatar/discuss.codechef.com/zexx/32/205589_2.png) [@zexx](https://discuss.codechef.com/u/zexx)\
**Post date:** [November 3, 2021, 11:00pm UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/5 "2021-11-03T23:00:30Z")

</div>

I used Segment tree on the euler tour of the tree for this question

---

<div class="post-metadata">

**Author:** ![lameboredginie](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@lameboredginie](https://discuss.codechef.com/u/lameboredginie)\
**Post date:** [November 4, 2021, 3:02am UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/6 "2021-11-04T03:02:43Z")

</div>

I have done the same thing but i why i am getting wa Need help  
[https://www.codechef.com/viewsolution/53439929](https://www.codechef.com/viewsolution/53439929)

---

<div class="post-metadata">

**Author:** ![lameboredginie](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@lameboredginie](https://discuss.codechef.com/u/lameboredginie)\
**Post date:** [November 4, 2021, 3:10am UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/7 "2021-11-04T03:10:06Z")

</div>

i just forgot to initailze ans variable to 0 for each test case.Too much pain 😢 and tried to debug it straight two hours in contest

---

<div class="post-metadata">

**Author:** ![saini\_abhishek](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@saini\_abhishek](https://discuss.codechef.com/u/saini_abhishek)\
**Post date:** [November 4, 2021, 5:04am UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/8 "2021-11-04T05:04:57Z")

</div>

WHY Rerooting the tree does’nt work. First i have calculated the answer for Node 1 and then did another DFS traversal and calculated the answer for each node by rerooting.  
Here is my code

> **[Online Compiler and IDE - GeeksforGeeks](https://ide.geeksforgeeks.org/E2BtFFz6BK)**
>
> Compile and run your code with ease on GeeksforGeeks Online IDE. GFG online compiler supports multiple languages like C, C++, Python, Java, NodeJS and more. Try it now on ide.geeksforgeeks.org

---

<div class="post-metadata">

**Author:** ![shivanshj](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shivanshj/32/24644_2.png) [@shivanshj](https://discuss.codechef.com/u/shivanshj)\
**Post date:** [November 4, 2021, 8:17am UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/9 "2021-11-04T08:17:48Z")

</div>

Rerooting does work, I have used it too and got AC. You can check out my submission.  
[https://www.codechef.com/viewsolution/53441784](https://www.codechef.com/viewsolution/53441784)

Here subgin (i) means the gcd of all nodes in subtree of node i (including node i) and subgout (i) means gcd of all nodes except in the subtree of i. (Excluding node i).

---

<div class="post-metadata">

**Author:** ![yogesh\_kumar\_m](https://discuss.codechef.com/user_avatar/discuss.codechef.com/yogesh_kumar_m/32/24644_2.png) [@yogesh\_kumar\_m](https://discuss.codechef.com/u/yogesh_kumar_m)\
**Post date:** [November 4, 2021, 10:40am UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/10 "2021-11-04T10:40:50Z")

</div>

[Rerooting works](https://www.codechef.com/viewsolution/53458091)  
Your code fails in the following test case:

```auto
1
6
2 1
6 5
4 1
3 6
2 5
7 62 54 49 84 34 

```

Expected answer: 55  
Your answer: 56

---

<div class="post-metadata">

**Author:** ![dark0haze](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@dark0haze](https://discuss.codechef.com/u/dark0haze)\
**Post date:** [November 4, 2021, 10:40am UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/11 "2021-11-04T10:40:54Z")

</div>

did the same but got TLE. WBU?

---

<div class="post-metadata">

**Author:** ![saini\_abhishek](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@saini\_abhishek](https://discuss.codechef.com/u/saini_abhishek)\
**Post date:** [November 4, 2021, 12:03pm UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/12 "2021-11-04T12:03:29Z")

</div>

thanks for the help brother.

---

<div class="post-metadata">

**Author:** ![saini\_abhishek](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@saini\_abhishek](https://discuss.codechef.com/u/saini_abhishek)\
**Post date:** [November 4, 2021, 12:04pm UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/13 "2021-11-04T12:04:25Z")

</div>

thank you brother for this test case. Because of this, I am able to debug my older code.

---

<div class="post-metadata">

**Author:** ![batra\_akshat](https://discuss.codechef.com/user_avatar/discuss.codechef.com/batra_akshat/32/24644_2.png) [@batra\_akshat](https://discuss.codechef.com/u/batra_akshat)\
**Post date:** [November 4, 2021, 6:46pm UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/14 "2021-11-04T18:46:50Z")

</div>

I am not sure why I am getting Runtime Error ( SIGABRT) . I think I am closing following the editorial Solution as well . Can someone point out the mistake please . Here is a link to my [Solution](https://www.codechef.com/viewsolution/53471090).

---

<div class="post-metadata">

**Author:** ![mysteri0us](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mysteri0us/32/96916_2.png) [@mysteri0us](https://discuss.codechef.com/u/mysteri0us)\
**Post date:** [November 5, 2021, 7:06am UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/15 "2021-11-05T07:06:04Z")

</div>

The problem is much easier when the tree is flattered.

[https://www.codechef.com/viewsolution/53475723](https://www.codechef.com/viewsolution/53475723)

---

<div class="post-metadata">

**Author:** ![yashgarg111](https://discuss.codechef.com/user_avatar/discuss.codechef.com/yashgarg111/32/68136_2.png) [@yashgarg111](https://discuss.codechef.com/u/yashgarg111)\
**Post date:** [November 5, 2021, 7:41am UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/16 "2021-11-05T07:41:59Z")

</div>

Someone should tell them that difficulty should not be wrt experts

---

<div class="post-metadata">

**Author:** ![abysswalkerr](https://discuss.codechef.com/user_avatar/discuss.codechef.com/abysswalkerr/32/98782_2.png) [@abysswalkerr](https://discuss.codechef.com/u/abysswalkerr)\
**Post date:** [November 5, 2021, 12:53pm UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/17 "2021-11-05T12:53:13Z")

</div>

What i thought of was of removing parent of some leaf node… greedily i choose to delete that parent that has maximum sum of values of its children . Can anybody help me in figuring out where it might go wrong

---

<div class="post-metadata">

**Author:** ![tbh\_12](https://discuss.codechef.com/user_avatar/discuss.codechef.com/tbh_12/32/24644_2.png) [@tbh\_12](https://discuss.codechef.com/u/tbh_12)\
**Post date:** [November 6, 2021, 11:40am UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/19 "2021-11-06T11:40:35Z")

</div>

My solution is exactly same as the editorial solution yet it is giving wrong answer. If someone can show me what I am doing wrong . Thanks in advance.  
[https://www.codechef.com/viewsolution/53547771](https://www.codechef.com/viewsolution/53547771)

---

<div class="post-metadata">

**Author:** ![mohitman](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mohitman/32/39280_2.png) [@mohitman](https://discuss.codechef.com/u/mohitman)\
**Post date:** [November 6, 2021, 7:06pm UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/20 "2021-11-06T19:06:54Z")

</div>

[My submission](https://www.codechef.com/viewsolution/53572403)  
Well written and easy to understand

---

<div class="post-metadata">

**Author:** ![zexx](https://discuss.codechef.com/user_avatar/discuss.codechef.com/zexx/32/205589_2.png) [@zexx](https://discuss.codechef.com/u/zexx)\
**Post date:** [December 25, 2021, 7:23pm UTC](https://discuss.codechef.com/t/dltnode-editorial/96044/21 "2021-12-25T19:23:24Z")

</div>

Mine passed!