1 #include <map>  2 #include <set>  3 #include <stack>  4 #include <queue>  5 #include <cmath>  6 #include <ctime>  7 #include <string>  8 #include <vector>  9 #include <cstdio> 10 #include <cstdlib> 11 #include <cstring> 12 #include <cassert> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker,"/STACK:102400000,102400000") 16 using namespace std; 17  18 #define N 100008                  19 #define LL long long 20 #define lson l,m,rt<<1 21 #define rson m+1,r,rt<<1|1  22 #define clr(x,v) memset(x,v,sizeof(x)); 23 #define bitcnt(x) __builtin_popcount(x) 24 #define rep(x,y,z) for (int x=y;x<=z;x++) 25 #define repd(x,y,z) for (int x=y;x>=z;x--) 26 const int mo  = 1000000007; 27 const int inf = 0x3f3f3f3f; 28 const int INF = 2000000000; 29 /**************************************************************************/  30  31 int T,n,m,k,sum,block,stop,cq2,tmp,label; 32 int lt[N],a[N],dep[N],st[N],ans[N],size[N],son[N],rk[N],w[N],top[N],mx[N<<2],cl[N],cr[N],fuck[N];; 33 int f[N][20]; 34 struct line{ 35     int u,v,nt; 36 }eg[N*2]; 37 struct que{ 38     int u,v,lca,k,id,flag; 39 }; 40 vector <que> q1[N],q2[N]; 41 void add(int u,int v){ 42     eg[++sum]=(line){u,v,lt[u]}; 43     lt[u]=sum; 44 } 45 void init(){ 46     clr(lt,0); clr(ans,0);   47     sum=1; tmp=0;  48 } 49 void dfs(int u,int fa){ 50     f[u][0]=fa; dep[u]=dep[fa]+1; size[u]=1; son[u]=0; 51     for (int i=lt[u];i;i=eg[i].nt){ 52         int v=eg[i].v; 53         if (v==fa) continue; 54         dfs(v,u); 55         size[u]+=size[v]; 56         if (size[v]>size[son[u]]) son[u]=v; 57     } 58 } 59 void dfs_2(int u,int tp){ 60     top[u]=tp; w[u]=++tmp; rk[tmp]=u; 61     if (son[u]) dfs_2(son[u],tp); 62     for (int i=lt[u];i;i=eg[i].nt){ 63         int v=eg[i].v; 64         if (v==f[u][0] || v==son[u]) continue; 65         dfs_2(v,v); 66     } 67 } 68 int lca(int x,int y){ 69     if (dep[x]<dep[y]) swap(x,y); 70     int d=dep[x]-dep[y]; 71     repd(i,18,0) 72         if (d & (1<<i)) x=f[x][i]; 73     if (x==y) return x; 74     repd(i,18,0) 75         if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; 76     return f[x][0]; 77 } 78 void work_1(int u){ 79     st[++stop]=u;   80     for (int i=0;i<q1[u].size();i++){ 81         int v=q1[u][i].v,x=q1[u][i].lca,k=q1[u][i].k,id=q1[u][i].id,flag=q1[u][i].flag; 82         if (flag) 83         { 84             int tmp=stop-k+1; 85             while (tmp>=0 && dep[st[tmp]]>=dep[x]){ 86                 ans[id]=max(ans[id],a[st[tmp]]); 87                 tmp-=k; 88             } 89         } 90         else 91         { 92             int tmp=dep[x]+ k - (dep[v]-dep[x]+1) % k ;  93             while (tmp<=stop && dep[st[tmp]]<=dep[u]){ 94                 ans[id]=max(ans[id],a[st[tmp]]); 95                 tmp+=k; 96             } 97         } 98     } 99     for (int i=lt[u];i;i=eg[i].nt){100         int v=eg[i].v;101         if (v==f[u][0]) continue;102         work_1(v);103     }104     st[stop--]=0;105 }106 int query(int L,int R,int l,int r,int rt){107     if (L<=l && r<=R){108         return mx[rt];109     }110     int m=(l+r)>>1;111     int res=0;112     if (L <= m) res=max(res,query(L,R,lson));113     if (m <  R) res=max(res,query(L,R,rson)); 114     return res;115 }116 117 void build(int l,int r,int rt){118     mx[rt]=0;119     if (l==r){120         mx[rt]=a[rk[fuck[l]]];121         return;122     }123     int m=(l+r)>>1;124     build(lson);125     build(rson);126     mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);127 }128 int calc(int L, int R, int k) {129     int l = lower_bound(fuck + cl[k], fuck + cr[k] + 1, L) - fuck;130     int r = upper_bound(fuck + cl[k], fuck + cr[k] + 1, R) - fuck - 1;131     return l <= r ? query(l,r,1,n,1) : 0;132 }133 void find(int tp,int x,int cl,int id){134     while (top[x]!=top[tp]){135         ans[id]=max(ans[id],calc(w[top[x]],w[x],cl));136         x=f[top[x]][0];137     }138     ans[id]=max(ans[id],calc(w[tp],w[x],cl));139 }140 141 vector <int> E[N];142 void work_2(int k){ 143     rep(i,0,k) E[i].clear();144     rep(i,1,n) E[(dep[rk[i]]) % k].push_back(i);145     label=0;146     rep(i,0,k-1){147         cl[i]=label+1;148         for (int j=0;j<E[i].size();j++)149             fuck[++label]=E[i][j];150         cr[i]=label;151         152     }153     build(1,n,1);154     for (int i=0;i<q2[k].size();i++){155         int u=q2[k][i].u,v=q2[k][i].v,x=q2[k][i].lca,id=q2[k][i].id;156         int tmp1=(dep[x]+(dep[u]-dep[x]+1) % k) % k;157         int tmp2=(dep[x]+k-(dep[u]-dep[x]+1) % k) % k;158         find(x,u,tmp1,id);159         find(x,v,tmp2,id);160     }161 }162 int main(){163     int cas=0;164     scanf("%d",&T);165     while (T--){166         printf("Case #%d:\n",++cas );167         init();168         scanf("%d%d",&n,&m);169         rep(i,1,n) scanf("%d",&a[i]);170         rep(i,1,n-1){171             int u,v;172             scanf("%d%d",&u,&v);173             add(u,v); add(v,u);174         }175         dfs(1,0);176         dfs_2(1,1);177         rep(j,1,18)178             rep(i,1,n)179                 f[i][j]=f[f[i][j-1]][j-1]; 180         block=20;181         cq2=0; 182         rep(i,1,n) q1[i].clear();183         rep(i,1,n) q2[i].clear();184         rep(i,1,m){185             int u,v,k;186             scanf("%d%d%d",&u,&v,&k);187             int x=lca(u,v);188             if (k>block)189             {190                 q1[u].push_back((que){u,v,x,k,i,1});191                 q1[v].push_back((que){v,u,x,k,i,0});192             }193             else194             {195                 q2[k].push_back((que){u,v,x,k,i,1});196             }197         }   198         work_1(1); 199         rep(i,1,block) if (q2[i].size()) work_2(i);200         rep(i,1,m) printf("%d\n",ans[i]);201     }202 }