P4116 Qtree3 （黑白染色）

题目链接：https://www.luogu.org/problem/P4116
题意：
修改颜色的时候用异或，这里线段树维护的是此区间内第一个出现的黑点。因为是单点修改，所以标记下传啥的都不需要~~直接上区间最值线段树。
如果白点的话就赋值INF，防止参与查询。
树剖后用线段树来维护，维护最小值，黑点的值为
  1 #include <stdio.h>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <string>
  5 #include <algorithm>
  6 #include <queue>
  7 #include <vector>
  8 #include <math.h>
  9 #include <map>
 10 
 11 #define LL long long
 12 #define INF 0x3f3f3f3f
 13 using namespace std;
 14 const int maxn = 2e5 + 10;
 15 
 16 struct Edge{
 17     int to,next;
 18 }edge[maxn*2];
 19 
 20 int tot,head[maxn];
 21 
 22 void add_edge(int u,int v){
 23     edge[++tot] = Edge{v,head[u]};
 24     head[u] = tot;
 25 }
 26 
 27 int fa[maxn];
 28 int dep[maxn];
 29 int siz[maxn];
 30 int son[maxn];
 31 
 32 void dfs1(int u,int f){
 33     fa[u] = f;
 34     dep[u] = dep[f] + 1;
 35     siz[u] = 1;
 36     int maxsize = -1;
 37     for (int i=head[u];~i;i=edge[i].next){
 38         int v = edge[i].to;
 39         if (v == f)
 40             continue;
 41         dfs1(v,u);
 42         siz[u] += siz[v];
 43         if (siz[v] > maxsize){
 44             son[u] = v;
 45             maxsize = siz[v];
 46         }
 47     }
 48 }
 49 
 50 int tim;
 51 int dfn[maxn];
 52 int w[maxn];
 53 int top[maxn];
 54 
 55 void dfs2(int u,int t){
 56     dfn[u] = ++tim;
 57     top[u] = t;
 58     w[tim] = u;
 59     if (!son[u])
 60         return ;
 61     dfs2(son[u],t);
 62     for (int i=head[u];~i;i=edge[i].next){
 63         int v = edge[i].to;
 64         if (v == fa[u] || v == son[u])
 65             continue;
 66         dfs2(v,v);
 67     }
 68 }
 69 
 70 struct segment_tree{
 71     int l,r;
 72     int val;
 73 }tree[maxn*4];
 74 
 75 void pushup(int nod){
 76     tree[nod].val = min(tree[nod<<1].val,tree[(nod<<1)+1].val);
 77 }
 78 
 79 void build(int l,int r,int nod){
 80     tree[nod].l = l;
 81     tree[nod].r = r;
 82     if (l == r){
 83         tree[nod].val = INF;
 84         return ;
 85     }
 86     int mid = (l + r) >> 1;
 87     build(l,mid,nod<<1);
 88     build(mid+1,r,(nod<<1)+1);
 89     pushup(nod);
 90 }
 91 
 92 void modify(int x,int y,int change,int k=1){
 93     int l = tree[k].l,r = tree[k].r;
 94     if (x <= l && y >= r){
 95         if (change == 1)
 96             tree[k].val = l;
 97         else
 98             tree[k].val = INF;
 99         return ;
100     }
101     int mid = (l + r) >> 1;
102     if (x <= mid){
103         modify(x,y,change,k<<1);
104     }
105     if (y > mid){
106         modify(x,y,change,(k<<1)+1);
107     }
108     pushup(k);
109 }
110 
111 int query(int x,int y,int k=1){
112     int l = tree[k].l,r = tree[k].r;
113     if (x <= l && y >= r){
114         return tree[k].val;
115     }
116     int mid = (l + r) >> 1;
117     int ret = INF;
118     if (x <= mid){
119         ret = min(ret,query(x,y,k<<1));
120     }
121     if (y > mid){
122         ret = min(ret,query(x,y,(k<<1)+1));
123     }
124     return ret;
125 }
126 
127 int query_from(int x,int y){
128     int ret = INF;
129     while (top[x] != top[y]){
130         if (dep[top[x]] < dep[top[y]])
131             swap(x,y);
132         ret = min(ret,query(dfn[top[x]],dfn[x]));
133         x = fa[top[x]];
134     }
135     if (dep[x] > dep[y])
136         swap(x,y);
137     ret = min(ret,query(dfn[x],dfn[y]));
138     return ret;
139 }
140 int color[maxn];
141 int main(){
142     int n,m;
143     scanf("%d%d",&n,&m);
144     memset(head,-1, sizeof(head));
145     for (int i=1;i<=n-1;i++){
146         int x,y;
147         scanf("%d%d",&x,&y);
148         add_edge(x,y);
149         add_edge(y,x);
150     }
151     dfs1(1,0);
152     dfs2(1,1);
153     build(1,n,1);
154     while (m--){
155         int op,x;
156         scanf("%d%d",&op,&x);
157         if (op == 0){
158             color[x] ^= 1;
159             modify(dfn[x],dfn[x],color[x]);
160         }
161         else {
162             int val = query_from(1,x);
163             if (val == INF)
164                 puts("-1");
165             else {
166                 printf("%d\n",w[val]);
167             }
168         }
169     }
170     return 0;
171 }