https://www.luogu.com.cn/problem/P4592
和题解对了半天愣是找不出错误
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=6.2e6+5;
int n,m,cnt,tot,dfnl[N],dfnr[N],rt1[N],rt2[N],a[N],fa[N][20],dep[N],s[M][2],Siz[M];
vector<int>v[N];
void ins(int &x,int k,int i)
{
cnt++;
s[cnt][0]=s[x][0],s[cnt][1]=s[x][1],Siz[cnt]=Siz[x]+1;
x=cnt;
if(i>=0) ins(s[x][k>>i&1],x,i-1);
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;--i)
if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=19;i>=0;--i)
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
return fa[x][0];
}
void dfs(int x,int father)
{
dfnl[x]=++tot;
dep[x]=dep[father]+1;
fa[x][0]=father;
for(int i=1;i<=19;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
cout<<tot<<" "<<a[x]<<endl;
ins(rt1[tot]=rt1[tot-1],a[x],19);
ins(rt2[x]=rt2[father],a[x],19);
for(auto i:v[x])
{
if(i==father) continue;
dfs(i,x);
}
dfnr[x]=tot;
}
int query(int x,int y,int k,int i)
{
if(i==-1) return 0;
int t=(k>>i&1);
if(Siz[s[x][t^1]]>Siz[s[y][t^1]]) return query(s[x][t^1],s[y][t^1],k,i-1)+(1<<i);
return query(s[x][t],s[y][t],k,i-1);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<n;++i)
{
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
while(m--)
{
int op,x,y,val;
cin>>op;
if(op==1)
{
cin>>x>>val;
cout<<query(rt1[dfnr[x]],rt1[dfnl[x]-1],val,19)<<"\n";
}
if(op==2)
{
cin>>x>>y>>val;
int t=lca(x,y);
cout<<max(query(rt2[x],rt2[fa[t][0]],val,19),query(rt2[y],rt2[t],val,19))<<"\n";
}
}
return 0;
}