题解 CF165D 【Beard Graph】

这就是一个树剖裸题，但给的是边权。 这题会板子的话，只需考虑如何来写线段树维护这道题维护的东西和边权化点权。 我对于边权化点权是在两点连线之间建立一个点，把边 权给它，节点数就会变为$2*n+1$，而代表边的点编号都为边的编号加n。 每次修改的时候把x改成x+n就是要修改边所对应的的编号。 对于黑边，给它赋值为1，而白边赋值为0，修改就是单点修改，查询的话，查询区 间和，再利用树剖LCA判断两点之间的距离是否是ans的2倍，若是，则全是黑边， 若不是则输出-1。然后这题就做完了。 AC代码 ```cpp #include<iostream> #include<cstdio> #define lson k<<1,l,mid #define rson k<<1|1,mid+1,r #define ls k<<1 #define rs k<<1|1 #define mid ((l+r)>>1) using namespace std; const int N=200005; int n,m,cnt,tot,ans; int head[N],id[N],top[N],fa[N],siz[N],son[N],dep[N],dfn[N]; int tr[N<<2]; bool flag; struct node{ int to,nxt; }e[N<<1]; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();} return s*w; } inline void add(int from,int to){ e[++cnt]=(node){to,head[from]}; head[from]=cnt; } void dfs1(int x,int f){ dep[x]=dep[f]+1;fa[x]=f;siz[x]=1; int y; for(int i=head[x];i;i=e[i].nxt){ y=e[i].to; if(y==f)continue; dfs1(y,x); siz[x]+=siz[y]; if(siz[y]>siz[son[x]])son[x]=y; } } void dfs2(int x,int topf){ top[x]=topf;id[x]=++tot;dfn[tot]=x; if(!son[x])return ; dfs2(son[x],topf); int y; for(int i=head[x];i;i=e[i].nxt){ y=e[i].to; if(y==fa[x]||y==son[x])continue; dfs2(y,y); } } inline void update(int k){ tr[k]=tr[ls]+tr[rs]; } void build(int k,int l,int r){ if(l==r){ tr[k]=dfn[l]>n?1:0; return ; } build(lson);build(rson); update(k); } void change(int k,int l,int r,int x,int y){ if(l==r&&x==l){ tr[k]=y; return ; } if(x<=mid)change(lson,x,y); else change(rson,x,y); update(k); } int ask(int k,int l,int r,int x,int y){ if(l==x&&y==r){ return tr[k]; } if(y<=mid)return ask(lson,x,y); else if(x>mid)return ask(rson,x,y); else return ask(lson,x,mid)+ask(rson,mid+1,y); } inline void qurey(int x,int y){ ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); ans+=ask(1,1,n*2-1,id[top[x]],id[x]); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); ans+=ask(1,1,n*2-1,id[x],id[y]); } inline int LCA(int x, int y) { while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); x=fa[top[x]]; } return dep[x]<dep[y]?x:y; } inline void check(int x,int y){ int dis=dep[x]+dep[y]-2*dep[LCA(x,y)]; if(dis!=ans*2)flag=1; } int main(){ n=read(); int x,y; for(int i=1;i<n;++i){ x=read();y=read(); add(x,i+n);add(i+n,x); add(i+n,y);add(y,i+n); } dfs1(1,0); dfs2(1,1); build(1,1,n*2-1); m=read(); int opt; while(m--){ opt=read();x=read(); if(opt==1)change(1,1,n*2-1,id[x+n],1); else if(opt==2)change(1,1,n*2-1,id[x+n],0); else { flag=0; y=read(); qurey(x,y); check(x,y); if(flag)printf("-1\n"); else printf("%d\n",ans); } } } ```