526互联

2022东北四省赛 F. Tree Path

发布时间 2023-03-30 15:46:54作者: qdhys

传送门

#include <iostream>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <queue>
#include <numeric>
#include <cassert>
#include <bitset>
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <tuple>
#include <array>
 
#define all(a) a.begin(), a.end()
#define cnt0(x) __builtin_ctz(x)
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define cntone(x) __builtin_popcount(x)
#define db double
#define fs first
#define se second
#define AC main(void)
#define ls(u) u << 1
#define rs(u) u << 1 | 1
typedef std::pair<int, int> PII;
#define HYS std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
const long double eps = 1e-9;
int MOD = 571373;
const int LO = 1 << 20 | 1;
char buffer[LO],*S,*TT;
#define getchar() ((S==TT&&(TT=(S=buffer)+fread(buffer,1,LO,stdin),S==TT))?EOF:*S++)

namespace Fio {
    inline std::string sread() {
        std::string s = " ";
        char e = getchar();
        while (!isdigit(e) && !isalpha(e) && e != '*') e = getchar();
        while (isdigit(e) || isalpha(e) || e == '*') s += e, e = getchar();
        return s;
    }
    
    inline int read() {
        int x = 0, y = 1;
        char c = getchar();
        while (!isdigit(c)) {
            if (c == '-') y = -1;
            c = getchar();
        }
        while (isdigit(c)) {
            x = (x << 3) + (x << 1) + (c ^ 48);
            c = getchar();
        }
        return x *= y;
    }
    
    inline ll readll() {
        ll x = 0, y = 1;
        char c = getchar();
        while (!isdigit(c)) {
            if (c == '-') y = -1;
            c = getchar();
        }
        while (isdigit(c)) {
            x = (x << 3) + (x << 1) + (c ^ 48);
            c = getchar();
        }
        return x *= y;
    }
    inline void write(ll x) {
        if (x < 0) x = -x, putchar('-');
        ll sta[35], top = 0;
        do sta[top++] = x % 10, x /= 10;
        while (x);
        while (top) putchar(sta[--top] + '0');
        putchar('\n');
    }
    
    inline void write(int x) {
        if (x < 0) x = -x, putchar('-');
        int sta[35], top = 0;
        do sta[top++] = x % 10, x /= 10;
        while (x);
        while (top) putchar(sta[--top] + '0');
        putchar('\n');
    }
} using namespace Fio;

const int N = 1e5 + 10, M = N << 2;
const int INF = 0x3f3f3f3f;

int min(int a, int b)	{return a > b ? b : a;}
int max(int a, int b)	{return a > b ? a : b;}

int n , m, _;

int d1[] = {0, 0, 1, -1};
int d2[] = {1, -1, 0, 0};

int w[N], h[N], e[M], ne[M], idx;
int id[N], nw[N], cnt;
int dep[N], sz[N], top[N], fa[N], son[N], ans[N];

std::vector<int> v[M];
int pos[M];
int del;

struct Node{
	int l, r;
}tr[M];

struct Segment{
	int x, y;
	bool operator <(const Segment& a) const{
		return x < a.x;
	}
}seg[N];

inline void build(int u, int l, int r){
	tr[u] = {l, r};
	if(l == r)	return ;
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
}

inline void init(){
	memset(h, -1, sizeof h);
}

inline void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
//统计子树大小 并且 找出重儿子
inline void dfs1(int u, int father, int depth){
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

//dfs序 nw标记dfs为cnt的时候对应的树上点的权值 top标记父亲是谁
inline void dfs2(int u, int t){
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void update(int u, int l, int r, int k){
	if(tr[u].l >= l && tr[u].r <= r){
		v[u].push_back(k);
		return ;
	}	
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	if(l <= mid)	update(u << 1, l, r, k);
	if(r > mid)	update(u << 1 | 1, l, r, k);
}

//传进来想要爬的两个点
inline void update_path(int u, int v, int k){
	int ct = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
        seg[ct ++] = {id[top[u]], id[u]};
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) std::swap(u, v);
    seg[ct ++] = {id[v], id[u]};
    int last = 1;
    std::sort(seg, seg + ct);
    for(int i = 0; i < ct; i ++){
    	if(last < seg[i].x)	update(1, last, seg[i].x - 1, k);
    	last = seg[i].y + 1;
    }
	if(last <= n) update(1, last, n, k);	
}

inline int query(int u, int x){
	while(pos[u] < v[u].size() && v[u][pos[u]] <= del) pos[u] ++;
	if(tr[u].l == tr[u].r)	return pos[u] == v[u].size() ? INF : v[u][pos[u]];
	
	int res = pos[u] == v[u].size() ? INF : v[u][pos[u]];
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid)	res = min(res, query(u << 1, x));
	else res = min(res, query(u << 1 | 1, x));
	
	return res;
}

int stk[N];

inline void Init(){
	dfs1(1, -1, 1);
    dfs2(1, 1);
}

inline void solve(){
	n = read(), m = read();
	int k = read();
	memset(h, -1, sizeof h);

	for(int i = 1; i < n; i ++){
		int a = read(), b = read();
		add(a, b);
		add(b, a);
	}

	build(1, 1, n);
	Init();
	
	std::vector<std::array<int, 3>> q;
	for(int i = 1; i <= m; i ++){
		int a = read(), b = read(), v = read();
		q.push_back({v, a, b});
	}

	std::sort(q.begin(), q.end());
	
	int mn = 1;
	for(auto &[v, a, b] : q){
		update_path(a, b, mn);
		stk[mn ++] = v;
	}
	
	int last = 0;
	while(k --){
		int op = read();
		if(op){
			int x = read();
			x ^= last;
			int t = query(1, id[x]);

			last = t == INF ? -1 : stk[t];
			write(last);
		}else{
			del ++;
		}
	}
}

int main(){

	_ = 1;
  	//_ = read();
	while(_ --)
    	solve();

    return 0;
}