题目描述
给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白
有两种操作：
0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑）
1 v : 询问1到v的路径上的第一个黑点，若无，输出-1
输入输出格式
输入格式：
第一行 N，Q，表示N个点和Q个操作
第二行到第N行N-1条无向边
再之后Q行，每行一个操作"0 i" 或者"1 v" (1 ≤ i, v ≤ N).
输出格式：
对每个1 v操作输出结果
树剖搞搞就行了qwq
对于线段树维护，若单点([q,q])为黑点，(ans[cur]=q)。否则为-1。
关于上传，优先选择左儿子的非-1答案，若左儿子ans=-1，选择右儿子答案。
记得输出的时候应该输出节点的初始编号，而不是树剖处理的新编号。新编号的时候标记一下即可。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAXN 100233
using namespace std;
int n,m;
int tot=0,cnt=0;
struct qwq
{
int nex,to;
}e[MAXN<<1];
int h[MAXN];
int fa[MAXN],top[MAXN],son[MAXN],dep[MAXN],siz[MAXN],id[MAXN];
int w[MAXN]={};
int ans[MAXN<<2];
int nid[MAXN];
inline void add(int x,int y)
{
e[++tot].to=y;
e[tot].nex=h[x];
h[x]=tot;
}
void dfs_fir(int x,int f,int dept)
{
dep[x]=dept;
fa[x]=f;
siz[x]=1;
int maxn=-1;
for (int i=h[x],y;i;i=e[i].nex)
{
y=e[i].to;
if (y==f) continue;
dfs_fir(y,x,dept+1);
siz[x]+=siz[y];
if (siz[y]>maxn)
{
son[x]=y;
maxn=siz[y];
}
}
}
void dfs_sec(int x,int ft)
{
top[x]=ft;
id[x]=++cnt;
nid[cnt]=x;
if (!son[x]) return;
dfs_sec(son[x],ft);
for (int i=h[x],y;i;i=e[i].nex)
{
y=e[i].to;
if (y==son[x]||y==fa[x]) continue;
dfs_sec(y,y);
}
}
#define leftson cur<<1
#define rightson cur<<1|1
#define mid ((l+r)>>1)
#define push_up if (ans[leftson]!=-1) { ans[cur]=ans[leftson]; return; } if (ans[rightson]!=-1) { ans[cur]=ans[rightson];return; } ans[cur]=-1
void build(int cur,int l,int r)
{
if (l==r)
{
ans[cur]=-1;
return;
}
build(leftson,l,mid);
build(rightson,mid+1,r);
push_up;
}
void change(int adn,int cur,int l,int r)
{
if (l==r)
{
if (ans[cur]!=-1)
{
ans[cur]=-1;
return;
}
ans[cur]=l;
return;
}
if (adn<=mid) change(adn,leftson,l,mid);
else change(adn,rightson,mid+1,r);
push_up;
}
int query(int ql,int qr,int cur,int l,int r)
{
if (ql<=l&&r<=qr)
{
return ans[cur];
}
if (ql<=mid)
{
int ans_a=query(ql,qr,leftson,l,mid);
if (ans_a!=-1)
{
return ans_a;
}
}
if (qr>mid) return query(ql,qr,rightson,mid+1,r);
return -1;
}
int query_(int x,int y)
{
int ans_a,ans_b=-1;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ans_a=query(id[top[x]],id[x],1,1,n);
// printf("::::::%d
",ans_a);
if (ans_b==-1)
{
ans_b=ans_a;
}
else if (ans_a!=-1)
{
ans_b=min(ans_a,ans_b);
}
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ans_a=query(id[x],id[y],1,1,n);
// printf("::::::::::::%d
",ans_a);
if (ans_b==-1) ans_b=ans_a;
else if (ans_a!=-1) ans_b=min(ans_a,ans_b);
return ans_b;
}
/*inline void DEBUG(int cur,int l,int r)
{
if (l==r)
{
printf("%d ",ans[cur]);
return;
}
DEBUG(leftson,l,mid);
DEBUG(rightson,mid+1,r);
}*/
int main()
{
scanf("%d%d",&n,&m);
int x,y;
for (int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs_fir(1,1,1);
dfs_sec(1,1);
build(1,1,n);
for (int i=1,answer;i<=m;i++)
{
scanf("%d%d",&x,&y);
if (!x)
{
change(id[y],1,1,n);
// printf("#########################::%d
",query(1,5,1,1,n));
// DEBUG(1,1,n);
// printf("
");
continue;
}
answer=query_(1,y);
if (answer==-1) printf("-1
");
else printf("%d
",nid[answer]);
}
return 0;
}
orz学长我真的不知道怎么就写到模拟赛原题了
sto学长对不起虽然是原题我还是爆零了