HDU-4812

题意见 https://vjudge.net/problem/HDU-4812

点分治板子，已经调了 2h+ 了/ll

蒯了网上的题解对拍没拍出锅来，求调/Hack

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, P = 1e6 + 3;
typedef pair<int, int> PII;

int n, k, siz[N], rt, mx[N], all, dis[N], inv[P], pnt[P], val[N];
PII ans;
bool vis[N];
vector<PII> des;
vector<int> tag, G[N];

int pw(int a, int b = P - 2, int p = P, int r = 1) {
  for (; b; b >>= 1, a = 1ll * a * a % p)
    if (b & 1)
      r = 1ll * r * a % p;
  return r;
}
void getRt(int u, int fa) {
  siz[u] = 1, mx[u] = 0;
  for (int i = 0; i < G[u].size(); ++i) {
    int v = G[u][i];
    if (v == fa || vis[v])
      continue;
    getRt(v, u), siz[u] += siz[v], mx[u] = max(mx[u], siz[v]);
  }
  mx[u] = max(mx[u], all - siz[u]);
  if (mx[u] < mx[rt])
    rt = u;
}
void getDs(int u, int fa) {
  des.push_back(make_pair(dis[u] = 1ll * dis[u] * val[u] % P, u));
  for (int i = 0; i < G[u].size(); ++i) {
    int v = G[u][i];
    if ((v - fa) && (!vis[v]))
      dis[v] = dis[u], getDs(v, u);
  }
}
void dfs(int u) {
  vis[u] = 1, pnt[val[u]] = u;
  tag = {val[u]};
  for (int fk = 0; fk < G[u].size(); ++fk) {
    int v = G[u][fk];
    if (vis[v])
      continue;
    des.clear();
    dis[v] = val[u], getDs(v, u);
    for (int i = 0; i < des.size(); ++i) {
      int w = des[i].first, id = des[i].second,
          iv = 1ll * k * inv[w] % P * 1ll * val[u] % P;
      if (pnt[iv] <= n)
        ans = min(ans, make_pair(min(pnt[iv], id), max(pnt[iv], id)));
    }
    for (int i = 0; i < des.size(); ++i)
      tag.emplace_back(des[i].first),
          pnt[des[i].first] = min(pnt[des[i].first], des[i].second);
  }
  for (int i = 0; i < tag.size(); ++i)
    pnt[tag[i]] = 1e9;
  for (int i = 0; i < G[u].size(); ++i) {
    int v = G[u][i];
    if (!vis[v])
      mx[rt = 0] = n, all = siz[v], getRt(v, u), dfs(rt);
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  inv[1] = 1;
  for (int i = 2; i < P; i++)
    inv[i] = 1LL * (P - P / i) * inv[P % i] % P;
  while (cin >> n) {
    cin >> k, mx[0] = all = n, ans = {1e9, 1e9};
    for (int i = 0; i < P; ++i)
      pnt[i] = 1e9;
    for (int i = 1; i <= n; ++i)
      G[i].clear(), vis[i] = 0;
    for (int i = 1; i <= n; ++i)
      cin >> val[i];
    for (int i = 1, u, v; i < n; ++i)
      cin >> u >> v, G[u].push_back(v), G[v].push_back(u);
    getRt(1, 0), dfs(rt);
    if (ans.first != 1e9)
      cout << ans.first << ' ' << ans.second << '\n';
    else
      cout << "No solution\n";
  }
  return 0;
}