- 1
- /*by SilverN*/
- 2#include 3#include 4#include 5#include 6#include 7#include 8#include 9#define LL long long 10 using namespace std;
- 11 const int mod = 1e6 + 3;
- 12 const int mxn = 120010;
- 13 int read() {
- 14 int x = 0,
- f = 1;
- char ch = getchar();
- 15
- while (ch < '0' || ch > '9') {
- if (ch == ' - ') f = -1;
- ch = getchar();
- }
- 16
- while (ch >= '0' && ch <= '9') {
- x = x * 10 + ch - '0';
- ch = getchar();
- }
- 17
- return x * f;
- 18
- }
- 19 struct edge {
- int v,
- nxt;
- }
- e[mxn << 1];
- 20 int hd[mxn],
- mct = 0;
- 21 void add_edge(int u, int v) {
- e[++mct].v = v;
- e[mct].nxt = hd[u];
- hd[u] = mct;
- return;
- }
- 22 int n,
- K;
- 23 LL w[mxn];
- 24 //
- 25 int mc[mxn],
- sz[mxn],
- rt,
- smm;
- 26 LL dis[mxn];
- 27 bool vis[mxn];
- 28 //map<int,int>mp;
- 29 int mp[mxn * 11];
- 30 //
- 31 LL inv[mxn * 11];
- 32 void init() {
- 33 inv[1] = 1;
- 34
- for (int i = 2; i) {
- 35 inv[i] = (( - mod / i) * inv[mod % i] % mod + mod) % mod;
- 36
- }
- 37
- return;
- 38
- }
- 39 void DFS_sz(int u, int fa) {
- 40 sz[u] = 1;
- mc[u] = 0;
- 41
- for (int i = hd[u]; i; i = e[i].nxt) {
- 42
- if (e[i].v == fa || vis[e[i].v]) continue;
- 43 int v = e[i].v;
- 44 DFS_sz(v, u);
- 45 sz[u] += sz[v];
- 46 mc[u] = max(mc[u], sz[v]);
- 47
- }
- 48 mc[u] = max(mc[u], smm - mc[u]);
- 49
- if (mc[u] u; 50
- return; 51
- }
- 52 int st[mxn],
- top = 0;
- 53 int ans[2];
- 54 inline void upd(int x, int y) {
- 55
- if (x > y) swap(x, y);
- 56
- if (!ans[0] || ans[0] > x || (ans[0] == x && ans[1] > y)) {
- 57 ans[0] = x;
- ans[1] = y;
- 58
- }
- 59
- return;
- 60
- }
- 61 void clc(int u, int fa, int mode) {
- 62
- if (!mode) {
- 63 LL tmp = (K * inv[dis[u]] % mod + mod) % mod;
- 64
- if (mp[tmp]) {
- upd(u, mp[tmp]);
- }
- 65
- }
- 66
- else {
- 67
- if (!mp[dis[u]]) {
- mp[dis[u]] = u;
- st[++top] = dis[u];
- }
- 68
- else mp[dis[u]] = min(mp[dis[u]], u);
- 69
- }
- 70
- for (int i = hd[u]; i; i = e[i].nxt) {
- 71
- if (e[i].v == fa || vis[e[i].v]) continue;
- 72 int v = e[i].v;
- 73 dis[v] = dis[u] * w[v] % mod;
- 74 clc(v, u, mode);
- 75
- }
- 76
- return;
- 77
- }
- 78 void solve(int x) {
- 79 vis[x] = 1;
- 80 mp[w[x]] = x;
- 81
- for (int i = hd[x]; i; i = e[i].nxt) {
- 82
- if (vis[e[i].v]) continue;
- 83 int v = e[i].v;
- 84 dis[v] = w[v] % mod;
- 85 clc(v, x, 0);
- 86 dis[v] = w[x] * w[v] % mod;
- 87 clc(v, x, 1);
- 88
- }
- 89
- while (top) {
- 90 mp[st[top--]] = 0;
- 91
- }
- 92 mp[w[x]] = 0;
- 93
- for (int i = hd[x]; i; i = e[i].nxt) {
- 94
- if (vis[e[i].v]) continue;
- int v = e[i].v;
- 95 smm = sz[v];
- 96 rt = 0;
- 97 DFS_sz(v, 0);
- 98 solve(rt);
- 99
- }
- 100
- return;
- 101
- }
- 102 int main() {
- 103 int i,
- j,
- u,
- v;
- 104 init();
- 105
- while (scanf("%d%d", &n, &K) != EOF) {
- 106 memset(hd, 0, sizeof hd);
- mct = 0;
- 107 memset(vis, 0, sizeof vis);
- 108 ans[0] = ans[1] = 0;
- 109
- for (i = 1; i <= n; i++) w[i] = read();
- 110
- for (i = 1; i) {
- 111 u = read();
- v = read();
- 112 add_edge(u, v);
- 113 add_edge(v, u);
- 114
- }
- 115 ans[0] = ans[1] = 0;
- 116 smm = n;
- mc[rt = 0] = mod;
- 117 DFS_sz(1, 0);
- 118 solve(rt);
- 119
- if (!ans[0]) printf("No solution\n");
- 120
- else printf("%d %d\n", ans[0], ans[1]);
- 121
- }
- 122
- return 0;
- 123
- }
来源: http://www.bubuko.com/infodetail-1968868.html