题意：
给定一棵 n 个点的树,每个点有权值 Vi
问是否存在一条路径使得路径上所有点的权值乘积 mod(10^6 + 3) 为 K
输出路径的首尾标号,若有多解,输出字典序最小的解
对于100%的数据,有1≤n≤10^5,0≤K≤10^6+2,1≤vi ≤10^6+2
思路：RYZ作业
预处理逆元
哈希路径权值乘积的模数，保存编号用来查询
1 const mo=1000003; 2 var head,vet,next,len,flag,son:array[1..210000]of longint; 3 f:array[0..110000]of longint; 4 dis,a:array[0..110000]of int64; 5 q:array[1..110000,1..2]of longint; 6 exf:array[0..mo]of int64; 7 hash:array[0..mo]of longint; 8 n,m,i,j,tot,x,y,z,ans1,ans2,sum,root,top,k:longint; 9 10 procedure add(a,b:longint); 11 begin 12 inc(tot); 13 next[tot]:=head[a]; 14 vet[tot]:=b; 15 head[a]:=tot; 16 end; 17 18 function max(x,y:longint):longint; 19 begin 20 if x>y then exit(x); 21 exit(y); 22 end; 23 24 procedure swap(var x,y:longint); 25 var t:longint; 26 begin 27 t:=x; x:=y; y:=t; 28 end; 29 30 function getroot(u,fa:longint):longint; 31 var e,v:longint; 32 begin 33 son[u]:=1; f[u]:=0; 34 e:=head[u]; 35 while e<>0 do 36 begin 37 v:=vet[e]; 38 if (v<>fa)and(flag[v]=0) then 39 begin 40 getroot(v,u); 41 son[u]:=son[u]+son[v]; 42 f[u]:=max(f[u],son[v]); 43 end; 44 e:=next[e]; 45 end; 46 f[u]:=max(f[u],sum-f[u]); 47 if f[u]<f[root] then root:=u; 48 end; 49 50 procedure dfs(u,fa:longint); 51 var e,v:longint; 52 begin 53 inc(top); q[top,1]:=dis[u]; q[top,2]:=u; 54 e:=head[u]; 55 while e<>0 do 56 begin 57 v:=vet[e]; 58 if (v<>fa)and(flag[v]=0) then 59 begin 60 dis[v]:=dis[u]*a[v] mod mo; 61 dfs(v,u); 62 end; 63 e:=next[e]; 64 end; 65 end; 66 67 procedure cmp(x,id:longint); 68 var y:longint; 69 begin 70 x:=exf[x]*k mod mo; 71 y:=hash[x]; 72 if y=0 then exit; 73 if y>id then swap(y,id); 74 if (y<ans1)or((y=ans1)and(id<ans2)) then 75 begin 76 ans1:=y; ans2:=id; 77 end; 78 end; 79 80 procedure solve(u:longint); 81 var e,v,i,now:longint; 82 begin 83 flag[u]:=1; hash[a[u]]:=u; 84 e:=head[u]; 85 while e<>0 do 86 begin 87 v:=vet[e]; 88 if flag[v]=0 then 89 begin 90 top:=0; dis[v]:=a[v]; 91 dfs(v,u); 92 for i:=1 to top do cmp(q[i,1],q[i,2]); //对于每一个子树，因为不能重复计算u这个根结点，分别计算子树内结果，后面再用加上根结点的答案更新 93 top:=0; dis[v]:=a[u]*a[v] mod mo; 94 dfs(v,u); 95 for i:=1 to top do 96 begin 97 now:=hash[q[i,1]]; 98 if (now=0)or(q[i,2]<now) then hash[q[i,1]]:=q[i,2]; //用子树中的路径加上根结点，更新经过根结点的答案 99 end; 100 end; 101 e:=next[e]; 102 end; 103 hash[a[u]]:=0; 104 e:=head[u]; 105 while e<>0 do 106 begin 107 v:=vet[e]; 108 if flag[v]=0 then 109 begin 110 top:=0; dis[v]:=a[u]*a[v] mod mo; 111 dfs(v,u); 112 for i:=1 to top do hash[q[i,1]]:=0; //清空所有信息 113 end; 114 e:=next[e]; 115 end; 116 e:=head[u]; 117 while e<>0 do 118 begin 119 v:=vet[e]; 120 if flag[v]=0 then 121 begin 122 root:=0; sum:=son[v]; 123 getroot(v,0); 124 solve(root); 125 end; 126 e:=next[e]; 127 end; 128 end; 129 130 begin 131 assign(input,'hdoj4812.in'); reset(input); 132 assign(output,'hdoj4812.out'); rewrite(output); 133 exf[0]:=1; exf[1]:=1; 134 for i:=2 to 1000003 do exf[i]:=exf[mo mod i]*(mo-mo div i) mod mo; 135 while not eof do 136 begin 137 // fillchar(head,sizeof(head),0); 138 //fillchar(flag,sizeof(flag),0); 139 for i:=1 to n do 140 begin 141 head[i]:=0; flag[i]:=0; 142 end; 143 tot:=0; ans1:=maxlongint; ans2:=maxlongint; 144 read(n,k); 145 if n=0 then break; 146 for i:=1 to n do read(a[i]); 147 for i:=1 to n-1 do 148 begin 149 read(x,y); 150 add(x,y); 151 add(y,x); 152 end; 153 root:=0; sum:=n; f[0]:=n+1; 154 getroot(1,0); 155 solve(root); 156 if ans1=maxlongint then writeln('No solution') 157 else writeln(ans1,' ',ans2); 158 end; 159 close(input); 160 close(output); 161 end.