记录编号	585490	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO19 DEC Gold]Milk Visits	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	2.156 s
提交时间	2023-12-13 20:31:57	内存使用	48.77 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
//主席树+树链剖分 
const int N = 2e5+10; 
int n,m;
struct made{
    int ver,nx;
}e[N<<1];
int hd[N],tot,cnt,num;
int fa[N],dep[N],son[N],size[N];
int a[N],rnk[N],dfn[N],top[N];
int root[N];
struct Tree{
    int rs,ls,dat;
}t[N<<4];
void build(int &x,int l,int r){
    x = ++num;t[x].dat = 0;
    if(l == r)return;
    int mid = l + r >> 1;
    build(t[x].ls,l,mid);
    build(t[x].rs,mid+1,r);
}
void change(int la,int &now,int l,int r,int z){
    now = ++num;
    t[now] = t[la];
    t[now].dat++;
    if(l == r)return;
    int mid = l + r >> 1;
    if(z <= mid)change(t[la].ls,t[now].ls,l,mid,z);
    else change(t[la].rs,t[now].rs,mid+1,r,z);
}
int ask(int now,int l,int r,int z){
    if(l == r)return t[now].dat;
    int mid = l + r >> 1;
    if(z <= mid)return ask(t[now].ls,l,mid,z);
    else return ask(t[now].rs,mid+1,r,z);
}
//------------------------
void add(int x,int y){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],hd[x] = tot;
}
void dfs1(int x){
    size[x] = 1;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(dep[y])continue;
        dep[y] = dep[x] + 1;
        fa[y] = x;
        dfs1(y);
        size[x] += size[y];
        if(!son[x] || size[y] > size[son[x]])son[x] = y;
    }
}
void dfs2(int x,int t){
    dfn[x] = ++cnt;
    rnk[cnt] = x;
    top[x] = t;
    if(!son[x])return;
    dfs2(son[x],t);
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y != fa[x] && y != son[x])dfs2(y,y);
    }
} 
int calask(int x,int y,int z){
    int ans = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        ans = ask(root[dfn[x]],1,n,z) - ask(root[dfn[top[x]]-1],1,n,z);
        if(ans > 0)return 1;
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y);
    ans = ask(root[dfn[y]],1,n,z) - ask(root[dfn[x]-1],1,n,z);
    if(ans > 0)return 1;
    return 0;
}
int main(){
    freopen("_milkvisits.in","r",stdin);
    freopen("_milkvisits.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
    for(int i = 1;i < n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dep[1] = 1;
    dfs1(1),dfs2(1,1);
    build(root[0],1,n);
    for(int i = 1;i <= n;i++)change(root[i-1],root[i],1,n,a[rnk[i]]);
    for(int i = 1;i <= m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        printf("%d",calask(x,y,z));
    }
    printf("\n");
    
    return 0;
    
}