rockdu
Problem Description
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 106 + 3) equals to K?
Can you help them in solving this problem?
Can you help them in solving this problem?
Input
There are several test cases, please process till EOF.
Each test case starts with a line containing two integers N(1 <= N <= 105) and K(0 <=K < 106 + 3). The following line contains n numbers vi(1 <= vi < 106 + 3), where vi indicates the integer on vertex i. Then follows N - 1 lines. Each line contains two integers x and y, representing an undirected edge between vertex x and vertex y.
Each test case starts with a line containing two integers N(1 <= N <= 105) and K(0 <=K < 106 + 3). The following line contains n numbers vi(1 <= vi < 106 + 3), where vi indicates the integer on vertex i. Then follows N - 1 lines. Each line contains two integers x and y, representing an undirected edge between vertex x and vertex y.
Output
For each test case, print a single line containing two integers a and b (where a < b), representing the two endpoints of the chain. If multiply solutions exist, please print the lexicographically smallest one. In case no solution exists, print “No solution”(without quotes) instead.
For more information, please refer to the Sample Output below.
For more information, please refer to the Sample Output below.
Sample Input
5 60 2 5 2 3 3 1 2 1 3 2 4 2 5 5 2 2 5 2 3 3 1 2 1 3 2 4 2 5
Sample Output
3 4 No solution Hint 1. “please print the lexicographically smallest one.”是指: 先按照第一个数字的大小进行比较，若第一个数字大小相同，则按照第二个数字大小进行比较，依次类推。 2. 若出现栈溢出，推荐使用C++语言提交，并通过以下方式扩栈： #pragma comment(linker,"/STACK:102400000,102400000")
Source
Recommend
liuyiding
点分治裸题，问乘积是K的路径，先线性处理逆元，然后就和 洛谷P4149 类似了。点分治每一层处理数组t[i]，表示之前子树中到根权值积在模意义下为i的序号最小的点。然后更新答案即可，这样常数会非常小。
#pragma comment(linker,"/STACK:102400000,102400000")
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5, P = 1e6 + 3;
const int maxp = 1e6 + 10, inf = 0x3f3f3f3f;
struct edge {
int v, next;
}e[maxn << 1];
int head[maxn], cnt, n, k, tot[maxp], w[maxn], u, v;
typedef pair<int, int > pii;
pii ans;
void adde(const int &u, const int &v) {
e[++cnt] = (edge) {v, head[u]};
head[u] = cnt;
}
int sum, rt, size[maxn], son[maxn], mud[maxn], inv[maxp], vis[maxn];
void Grt(int u, int fa) {
size[u] = 1, son[u] = 0;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == fa || vis[v]) continue;
Grt(v, u), size[u] += size[v];
son[u] = max(size[v], son[u]);
}
son[u] = max(son[u], sum - size[u]);
if(son[u] < son[rt]) rt = u;
}
void calc(int u, int p, int uw) {
mud[u] = int(1LL * mud[p] * w[u] % P);
int nxt = int(1LL * (1LL * k * inv[mud[u]] % P) * uw % P);
pii np;
if(tot[nxt]) {
if(tot[nxt] < u) np = make_pair(tot[nxt], u);
else np = make_pair(u, tot[nxt]);
if(np < ans) ans = np;
}
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == p || vis[v]) continue;
calc(v, u, uw);
}
}
void dfs(int u, int p, int add) {
if(!add || !tot[mud[u]]) tot[mud[u]] = add * u;
else if(tot[mud[u]] > u) tot[mud[u]] = u;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == p || vis[v]) continue;
dfs(v, u, add);
}
}
void solve(int u) {
mud[u] = w[u], tot[w[u]] = u, vis[u] = 1;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;if(vis[v]) continue;
calc(v, u, w[u]), dfs(v, u, 1);
}
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;if(vis[v]) continue;
dfs(v, u, 0);
}
tot[w[u]] = 0;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;if(vis[v]) continue;
rt = 0, sum = size[v], Grt(v, u), solve(rt);
}
}
signed main() {
inv[1] = 1;
for(register int i = 2; i < P; ++i) inv[i] = (-1LL * (P / i) * inv[P % i] % P + P) % P;
while(~scanf("%d%d", &n, &k)) {
son[0] = inf, cnt = 0;
ans = make_pair(inf, inf);
memset(head, 0, sizeof(head));
memset(vis, 0, sizeof(vis));
for(register int i = 1; i <= n; ++i) scanf("%d", &w[i]);
for(register int i = 1; i < n; ++i) scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
rt = 0, sum = n, Grt(1, 0);
solve(rt);
if(ans.first != inf) printf("%d %d\n", ans.first, ans.second);
else printf("No solution\n");
}
return 0;
}
没有帐号? 立即注册