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

Please help

Can anyone point out problem in my code. I am getting TLE for all cases except 1 case. I have commented my code thoroughly.

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

Please help

Can anyone point out problem in my code. I am getting TLE for all cases except 1 case. I have commented my code thoroughly.

Hi! Thanks for the question. Since you’re going to take coefficients modulo m_{l_i} in the end, it doesn’t matter. You may just take m-k instead of -k to obtain needed remainder.

I did not get the following things:

- Why is it assured the equation will have a solution if g/g’ and m/g’ are coprime?
- How can we substitute g with g’?

From the other answer, I can see that gcd is the interval which separates successive multiples of g’ but how can I prove that generally?

Any suggested reading that I should go through?

Pass graph “adj” by reference in your function. Everytime the function is called, graph is copied! Hence, TLE.

Solution for linear diophantine equation with co-prime numbers may be obtained by extended euclidean algorithm. We may substitute g with g' because equation g'=kg \pmod{m} has a solution so set of numbers which occur in arithmetic progression of g is the same as set of numbers which occur in arithmetic progression of g'.

Tried almost everything, but getting runtime error for first 9 testcases

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> tree[10001];
ll val[10001];
ll m[10001];
ll res[10001];
vector<ll> leaf;
ll _gcd(ll a, ll b){
if(a<b)
return _gcd(b,a);
if(b==0)
return a;
return _gcd(b,a%b);
}
void cal(int x, int p, ll gcd){
gcd = _gcd(gcd,val[x]);
for(auto u: tree[x]){
if(u==p)
continue;
cal(u,x,gcd);
}
if(tree[x].size()==1 && x!=1){
leaf.push_back(x);
res[x] = m[x]-_gcd(m[x],gcd);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
if(!leaf.empty())
leaf.clear();
for(int i=1; i<=n; i++)
tree[i].clear();
int a,b;
for(int i=0; i<n-1; i++){
cin>>a>>b;
tree[a].push_back(b);
tree[b].push_back(a);
}
for(int i=1; i<=n; i++)
cin>>val[i];
for(int i=1; i<=n; i++)
cin>>m[i];
cal(1,0,val[1]);
sort(leaf.begin(),leaf.end());
int sz = leaf.size();
for(int i=0; i<sz; i++)
cout<<res[leaf[i]]<<" ";
cout<<"\n";
}
return 0;
}
```

Your explanation made everything much easier. Thanks a lot for your patience and explanation.

you should be putting the `if(G[i].size()==1)`

in DFS, outside the `if(T[i] == false)`

.

input format says ‘there is an edge between x and y’ and not ‘there is an edge frm x to y’

hence input for was in that format thats why you shld choose undirected graph

assume the graph to be undirected if not given in ques for future probs