记录编号	451995	评测结果	AAAAAAAAAA
题目名称	[ICPC 2017西安区域赛]树上异或xor	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.160 s
提交时间	2017-09-18 19:36:07	内存使用	3.90 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register char tmp = getc();
    register int res = 0;
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

char ops[1 << 20], *opt = ops, *const opt_end = (ops + (1 << 20));

inline void write_all(void) { 
    fwrite(ops, 1, opt - ops, stdout);
    opt = ops; return ;
}

inline void write(int x) { 
    static char *p = new char[20]();
    do { 
        *(++p) = (x % 10) | 0x30;
        x /= 10;
    }while(x);
    while(*p) { 
        *(opt++) = *(p--);
        if(opt == opt_end) write_all();
    }
    *(opt++) = '\n';
    if(opt == opt_end) write_all();
    return ;
}

#define MAXN (50010)

struct EDGE{ 
    int to;
    EDGE *ne;
    EDGE(int t, EDGE *n) { 
        to = t, ne = n;
    }
};

void dfs(int u);
inline void add_edge(int fr, int to);
inline int work(int a, int b, int k);

EDGE *head[MAXN];
int dep[MAXN], fa[MAXN];
int val[MAXN], N, Q;

int main() { 
#ifndef LOCAL
    freopen("xor_xian.in", "r", stdin);
    freopen("xor_xian.out", "w", stdout);
#endif
    N = read(), Q = read();
    for(int i = 1; i < N; ++i) 
        add_edge(read(), read());
    for(int i = 1; i <= N; ++i) 
        val[i] = read();
    dfs(1);
    for(int i = 0, a, b, k; i < Q; ++i) { 
        a = read(), b = read(), k = read();
        write(work(a, b, k));
    }
    write_all();
    return 0;
}

void dfs(int u) { 
    for(register EDGE *e = head[u]; e; e = e->ne) { 
        if(dep[e->to]) continue;
        dep[e->to] = dep[u] + 1;
        fa[e->to] = u;
        dfs(e->to);
    }
    return ;
}

inline void add_edge(int fr, int to) { 
    head[fr] = new EDGE(to, head[fr]);
    head[to] = new EDGE(fr, head[to]);
    return ;
}

inline int work(int a, int b, int k) { 
    static vector<int> a1, a2;
    register int ans = 0;
    while(dep[a] > dep[b]) 
        a1.push_back(a), a = fa[a];
    while(dep[a] < dep[b]) 
        a2.push_back(b), b = fa[b];
    while(a ^ b) { 
        a1.push_back(a);
        a2.push_back(b);
        a = fa[a], b = fa[b];
    }
    a1.push_back(a);
    for(int i = a2.size() - 1; ~i; --i) 
        a1.push_back(a2[i]);
    for(unsigned i = 0; i < a1.size(); ++i) 
        if(!(i % k)) ans ^= val[a1[i]];
    a1.clear(); a2.clear();
    return ans;
}