This explanation is really intuitive

.

# SJ1 - Editorial

**vijju123**#24

I guess you are missing taran’s editorials more - I barely get time to serve as editorialist these days I am sure people would have forgotten how mine were like

**wingman_7**#26

thumbs up… it’s a great explanation, I see nowadays that the official editorials use a bit tough language and statements i.e. it’s not beginner friendly

**thesmartguy**#27

* "Life is too short to keep track of unwanted things"… * but seriously though I miss

**Chef’s Vijju Corner**.

**leo_euler**#28

@melfice It is mentioned in editorial that :

“

we always may find a linear combination which is equal to g , by extended euclids algorithm”

But in extended Euclid’s theorem the coefficients of a,b maybe negative i.e in the equation ax+by=gcd(a,b) , x and y maybe negative .

However it is clearly mentioned in the question

"For each node on this path (including the root and this leaf), choose anon-negative integerand multiply the value of this node by it "

**ashu769**#30

what is wrong in this code.please if you can debug it

https://www.codechef.com/viewsolution/24013940

**leo_euler**#32

@yuv_sust I agree that if D is not a multiple of G then surely there is no integral solution, however, I don’t see why the converse part is always true, that given any D=nG we can always get **non-negative coefficients A, B, C...** which satisfy the equation.

A simple example can be x=240 and y=46 with GCD(x,y) =G= 2 , lets say we want D=G (i.e n=1) here using extended Euclid’s theorem give us A=-9 and B=47 ( -9*240+47*46=2 ) , but in question it is clearly mentioned that the coefficients A,B with which we are multilpying the nodes must be positive.

"For each node on this path (including the root and this leaf), choose anon-negative integerand multiply the value of this node by it "

Unofficial Editorial of SJ1

**prajjwal_ctb**#34

Please Help me with this code.

It is giving me wrong answer in every test case.

But i manually tested a few cases, they’re running fine.

```
#include<iostream>
#include<vector>
#include<map>
#define lli long long int
using namespace std;
vector <lli> G[100001];
int V[100001];
int M[100001];
bool T[100001];
map <lli,lli> A;
lli GCD(lli a , lli b){
if(b == 0)
return a;
else
return GCD(b,a%b);
}
void DFS(lli i, lli gcdTillNow)
{
if(T[i]==false)
{
T[i]=true;
gcdTillNow=GCD(gcdTillNow,V[i]);
if(G[i].size()==1)// ie of leaf node
{
A[i]=M[i]-GCD(M[i],gcdTillNow);
}
else // if not leaf node
{
for(lli j=0;j<G[i].size();j++)
{
DFS(G[i][j],gcdTillNow);
}
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
for(lli i=0;i<100001;i++)
{
G[i].clear();
T[i]=false;
V[i]=0;
M[i]=0;
}
A.clear();
lli N;
cin>>N;
for(lli i=0;i<N-1;i++)
{
lli a,b;
cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
for(lli i=1;i<=N;i++)
cin>>V[i];
for(lli i=1;i<=N;i++)
cin>>M[i];
DFS(1,V[1]);
// printing ANS
map<lli,lli>::iterator it;
for(it=A.begin();it!=A.end();it++)
{
cout<<it->second<<" ";
}
cout<<endl;
}
return 0;
}
```

**taran_1407**#35

He is missing your corner thoughts. As for me, I have been barely keeping up college work and related things these days.

@vijju123 Legends are not forgotten.

**vijju123**#36

But if only my corner is being missed then that means I can extend my break . I will be back when my explanations get missed as well hehehehe

**karangreat234**#38

@vijju123 Sir,we are missing you badly. Our life is hollow without your editorials and chef vijju’s corner

**decode876**#39

Can someone please help me find my mistake in this??

https://www.codechef.com/viewsolution/24022307

**akshaycs**#40

@ melfice please help me, what is the bug in my program, it run perfectly in my computer but didn’t get AC https://www.codechef.com/viewsolution/24027788 this is the link i have use dictionary for storing tree as well as result

**malcolm_123ssj**#41

For all those who are getting TLE, try using fast input output. TLE arises because of the fact that computing gcd is a time consuming process.

**dibyenshu**#44

For those getting TLE with DFS (in c++) use

ios_base::sync_with_stdio(false);

cin.tie(0);

SJ1 and SUBREM had pretty bad constraints. The above two lines should never be necessary for getting AC.

Here is a post regarding the rant