题解 CF165D 【Beard Graph】
Farkas_W
·
·
题解
\text{关于题意}
原图
经过转化后的图(将边权转化为点权)
注意：对于路径$4-2-5$，只需访问点 $4$ 和点 $5$，对于 $4$ 和 $5$ 的 $LCA$ (最近公共祖先)不可取，因为 $2$ 在原图中对应的是边 $1-2$，并不在路径$4-2-5$上，所以在树链剖分中当 $x$ 和 $y$ 在同一条链上时($dep[x]<dep[y]$)，只需询问 $x+1$ 到 $y$ 的路径。
$$\text{对于三种操作}$$
1. 操作 $1$：修改操作，把第 $u$ 条边改成黑边。
2. 操作 $2$：修改操作，把第 $u$ 条边改成白边。
3. 操作 $3$：询问操作，若 $u$ 号节点和 $v$ 号节点间存在白边，输出 $-1$，否则输出 $u$ 号节点和 $v$ 号节点间的黑边数。
$\quad$可以很容易发现操作 $1$和操作 $2$ 其实是一种操作，只需开一个数组 $u$[$x$][$2$] 来记录第 $x$ 条边的两个端点，操作 $2$将这条边标记为 $0$，意为白边，操作 $1$ 就把这条边标记为 $1$，意为黑边，用线段树维护区间和(也可以是最小值)，询问时当$sum$[$k$]==$r$-$l$+$1$ 时说明这个区间内所有边都是黑边，ans+=sum[k]，否则至少有 $1$ 条边是白边，输出-1。
$\quad$下面贴出AC代码，建议反复阅读，深刻理解。
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#define il inline
#define inf 1e18
#define next nne
#define re register int
using namespace std;
il int read() //快速读入
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;
}
il void print(int x) //快速输出
{
if(x<0)putchar('-'),x=-x;
if(x/10)print(x/10);
putchar(x%10+'0');
}
const int N=3e5+5;
int n,m,next[N<<1],go[N<<1],head[N],tot,u[N][2],sum[N<<2];
int seg[N],son[N],father[N],top[N],size[N],dep[N],ans;
il void Add(int x,int y)
{
next[++tot]=head[x];
head[x]=tot;
go[tot]=y;
}
il void dfs1(int x,int fa)
{
father[x]=fa;dep[x]=dep[fa]+1;size[x]=1;
for(re i=head[x],y;i,y=go[i];i=next[i])
{
if(y==fa)continue;
dfs1(y,x);
size[x]+=size[y];
if(size[y]>size[son[x]])son[x]=y;
}
}
il void dfs2(int x,int topf)
{
top[x]=topf;seg[x]=++seg[0];
if(!son[x])return;
dfs2(son[x],topf);
for(re i=head[x],y;i,y=go[i];i=next[i])
{
if(top[y])continue;
dfs2(y,y);
}
}
il void build(int k,int l,int r)//建树，每个点初始为1，每条边都是黑边
{
if(l==r){sum[k]=1;return;}
int mid=l+r>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
il void change(int k,int l,int r,int x,int z)
{
if(z&&sum[k]==r-l+1)return;
if(l==r){sum[k]=z;return;}
int mid=l+r>>1;
if(x<=mid)change(k<<1,l,mid,x,z);
else change(k<<1|1,mid+1,r,x,z);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
il bool query1(int k,int l,int r,int x,int y)
{
if(x<=l&&y>=r){if(sum[k]==r-l+1){ans+=sum[k];return 1;}return 0;} //统计答案
int mid=l+r>>1;
if(x<=mid)if(!query1(k<<1,l,mid,x,y))return 0;
if(y>mid)if(!query1(k<<1|1,mid+1,r,x,y))return 0;
return 1;
}
il void change1(int x,int z)
{
int xx=u[x][0],yy=u[x][1];
if(father[xx]==yy)change(1,1,n,seg[xx],z); //修改儿子节点
else change(1,1,n,seg[yy],z);
}
il bool query(int x,int y)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
if(!query1(1,1,n,seg[fx],seg[x]))return 0;
x=father[fx];fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
if(seg[x]+1<=seg[y])if(!query1(1,1,n,seg[x]+1,seg[y]))return 0; //记得seg[x]+1
return 1;
}
signed main()
{
n=read();
for(re i=1;i<n;i++){re x=read(),y=read();u[i][0]=x;u[i][1]=y;Add(x,y);Add(y,x);}
dfs1(1,0);dfs2(1,1);build(1,1,n);tot=0;m=read();
while(m--)
{
re k=read(),x=read();
if(k==1)change1(x,1);
else if(k==2)change1(x,0);
else {re y=read();ans=0;if(query(x,y))print(ans);else print(-1);putchar('\n');} //ans记得要清零
}
return 0;
}
```
$$\text{后话}$$
$\quad$此题和[P3950 部落冲突](https://www.luogu.com.cn/problem/P3950)很像，那题也有[我的题解](https://www.luogu.com.cn/blog/Farkas/solution-p3950)，欢迎支持。
$\quad$谢谢观赏，写题解不易，点个赞吧！