SJ1 - prototype_96

#include<bits/stdc++.h>
using namespace std;
#define MAX 100009

vector<int> tree[MAX];
long long int values[MAX], rems[MAX];
long long int gcds[MAX]; // stores gcd of all nodes in the path from root to node i
int visited[MAX];

void solve(int x, int parent) {
    visited[x] = 1;
    gcds[x] = __gcd(gcds[parent], values[x]);
    for(int i = 0; i < tree[x].size(); i++) {
        if (!visited[tree[x][i]]) {
            solve(tree[x][i], x);
        }
    }
}
int main()
{
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;

        for(int i = 0; i < MAX; i++) tree[i].clear();
        int x, y;
        for(int i = 1; i < n; i++) {
            cin >> x >> y;
            tree[x].push_back(y);
        }

        for(int i = 1; i <= n; i++) {
            cin >> values[i];
        }
        for(int i = 1; i <= n; i++) {
            cin >> rems[i];
        }

        memset(gcds, 0, sizeof(gcds));
        memset(visited, 0, sizeof(visited));
        gcds[1] = values[1];
        solve(1, 1);

        for(int i = 2; i <= n; i++) {
            if (!tree[i].size()) {
                cout << rems[i] - __gcd(rems[i], gcds[i]) << " ";
            }
        }
        cout << endl;
    }
}

/*

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


//4 9 14
//20
//10
//8
//8
//8
*/