HDU4812

树分治
求逆元请递推，不然会TLE
开桶记录即可
注意常数

# pragma comment(linker,"/STACK:102400000,102400000")

# include <stdio.h>

# include <stdlib.h>

# include <iostream>

# include <algorithm>

# include <string.h>

# include <vector>

# define IL inline

# define RG register

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

IL ll Read(){

    RG char c = getchar(); RG ll x = 0, z = 1;

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';

    return x * z;

}

const int MAXN(200010), INF(2147483647), P(1e6 + 3);

int n, cnt, fst[MAXN], to[MAXN], nxt[MAXN], w[MAXN], k, ansx, ansy;

int size[MAXN], rt, sz, mx[MAXN], vis[MAXN], inv[P], d[P], S[MAXN], top, T[P];

IL void Add(RG int u, RG int v){  nxt[cnt] = fst[u]; to[cnt] = v; fst[u] = cnt++;  }

IL void Getroot(RG int u, RG int fa){

    size[u] = 1; mx[u] = 0;

    for(RG int e = fst[u]; e != -1; e = nxt[e]){

        if(vis[to[e]] || to[e] == fa) continue;

        Getroot(to[e], u);

        size[u] += size[to[e]];

        mx[u] = max(mx[u], size[to[e]]);

    }

    mx[u] = max(mx[u], sz - size[u]);

    if(mx[u] < mx[rt]) rt = u;

}

IL void Getdeep(RG int u, RG int fa, RG int dis){

    d[u] = dis; S[++top] = u;

    for(RG int e = fst[u]; e != -1; e = nxt[e]){

        if(vis[to[e]] || to[e] == fa) continue;

        Getdeep(to[e], u, 1LL * dis * w[to[e]] % P);

    }

}

IL void Solve(RG int u){

    vis[u] = 1; T[1] = u;

    for(RG int e = fst[u]; e != -1; e = nxt[e]){

        if(vis[to[e]]) continue;

        top = 0; Getdeep(to[e], u, w[to[e]]);

        for(RG int i = 1; i <= top; i++){

            RG int x = S[i], y = d[x], z = 0;

            z = T[1LL * k * inv[1LL * y * w[u] % P] % P];

            if(!z) continue;

            if(x > z) swap(x, z);

            if(x < ansx || (x == ansx && z < ansy)) ansx = x, ansy = z;

        }

        for(RG int i = 1; i <= top; i++) if(!T[d[S[i]]] || S[i] < T[d[S[i]]]) T[d[S[i]]] = S[i];

    }

    for(RG int e = fst[u]; e != -1; e = nxt[e]){

        if(vis[to[e]]) continue;

        top = 0; Getdeep(to[e], u, w[to[e]]);

        for(RG int i = 1; i <= top; i++) T[d[S[i]]] = 0;

    }

    T[1] = 0;

    for(RG int e = fst[u]; e != -1; e = nxt[e]){

        if(vis[to[e]]) continue;

        rt = 0; sz = size[to[e]];

        Getroot(to[e], u);

        Solve(rt);

    }

}

int main(RG int argc, RG char* argv[]){

    mx[0] = INF; inv[1] = 1;

    for(RG int i = 2; i < P; i++) inv[i] = (1LL * (-(P / i)) * inv[P % i] % P + P) % P;

    while(scanf("%d%d", &n, &k) != EOF){

        Fill(fst, -1); Fill(vis, 0);

        rt = cnt = 0; sz = n; ansx = ansy = n + 1;

        for(RG int i = 1; i <= n; i++) w[i] = Read();

        for(RG int i = 1, u, v; i < n; i++) u = Read(), v = Read(), Add(u, v), Add(v, u);

        Getroot(1, 0); Solve(rt);

        if(ansx > n) puts("No solution");

        else printf("%d %d\n", ansx, ansy);

    }

    return 0;

}