D Tree

题目描述

There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with $N$ vertices, while each branch can be treated as a vertex). Today the students under the tree are considering a problem: Can we find such a chain on the tree so that the multiplication of all integers on the chain (mod $10^6 + 3$) equals to $K$?
Can you help them in solving this problem?

代码

#include <cstdio>
#include <map>
#include <algorithm>
#include <cstring>
#define MOD 1000003
using namespace std;
struct edge {
int v, nxt;
} e[200001];
long long n, k, x, y, root, nume, tot, inv[MOD], h[100001], v[100001], size[100001], f[100001], val[100001];
bool vis[100001];
map<long long, int> id;
void add_edge(int u, int v) {
e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
e[++nume].v = u, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
size[t] = 1, f[t] = 0;
for (int i = h[t]; i; i = e[i].nxt) {
if (!vis[e[i].v] && e[i].v != fa) {
get_root(e[i].v, t);
size[t] += size[e[i].v];
f[t] = max(f[t], size[e[i].v]);
}
}
f[t] = max(f[t], tot - size[t]);
if (f[t] < f[root]) root = t;
}
void update(int a, int b) {
if (a > b) swap(a, b);
if (a < x) x = a, y = b;
else if (a == x && b < y) y = b;
}
void get_dist(int t, int fa, int flag) {
if (!flag) {
if (!id.count(val[t])) id[val[t]] = t;
else id[val[t]] = min(id[val[t]], t);
} else {
if (val[t] * val[root] % MOD == k) {
if (t <= x || root <= x) update(t, root);
}
long long inverse = k * inv[val[t]] % MOD * inv[val[root]] % MOD;
if (id.count(inverse)) {
if (id[inverse] <= x || t <= x) update(id[inverse], t);
}
}
for (int i = h[t]; i; i = e[i].nxt) {
if (!vis[e[i].v] && e[i].v != fa) {
if (flag) val[e[i].v] = val[t] * v[e[i].v] % MOD;
get_dist(e[i].v, t, flag);
}
}
}
void solve(int t) {
vis[t] = true, val[t] = v[t], id.clear();
for (int i = h[t]; i; i = e[i].nxt) {
if (!vis[e[i].v]) {
val[e[i].v] = v[e[i].v];
get_dist(e[i].v, t, 1);
get_dist(e[i].v, t, 0);
}
}
for (int i = h[t]; i; i = e[i].nxt) {
if (!vis[e[i].v]) {
root = 0, tot = size[e[i].v];
get_root(e[i].v, t);
solve(root);
}
}
}
int main()
{
inv[1] = 1;
for (int i = 2; i < MOD; ++i) {
inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
}
while (scanf("%lld%lld", &n, &k) != -1) {
x = y = 1e9, nume = 0;
memset(vis, 0, sizeof(vis));
memset(h, 0, sizeof(h));
for (int i = 1; i <= n; ++i) scanf("%lld", &v[i]);
for (int i = 1; i < n; ++i) {
int u, v;
scanf("%d%d", &u, &v);
}
tot = f[0] = n, root = 0;
get_root(1, 0);
solve(root);
if (y <= n) printf("%lld %lld\n", x, y);
else printf("No solution\n");
}
return 0;
}


418 I'm a teapot