洛谷P3250 网络 [HNOI2016] 整体二分
正解:整体二分+树状数组
解题报告:
亲这里的建议是用整体二分呢
dbq最近看sd淘宝说话体看多了有点脑抽,,,
首先考虑如果是单组询问怎么做昂QAQ
考虑二分答案
对于所有比mid小的操作都不用管
然后对于大于mid的操作,他们都是不应该存在的
怎么样就不会存在呢,那不然就是已经结束了不然就是经过了故障点嘛
所以如果能通过某种方式算出所有麻油结束的经过了故障点的链数就可以判断是否合法了嘛
然后这个其实是个比较典型的dfn序套路题,,,?
就是对每个修改就改链的两端+1(-1),两端的lca-1(+1),lca的父亲-1(+1)
然后查询经过点x的链有几条就相当于是查询x的子树中的权值和
( 然后这个套路我本来还想解释一下的,,,后来发现麻油什么好解释的昂QAQ
就理解成差分就好,然后为什么是lca-1,lca父亲-1,是为了保证lca处答案的正确性
感性理解趴,,,这个我也不能很好的解释,但是画个图还是不难理解的w
显然如果经过x的链的条数=大于mid的链且没有结束的条数说明枚举大了,ans在[l,mid]中
否则ans在[mid+1,r]中
然后看到多组询问什么的可以想到,整体二分
就依然是整体二分的经典套路昂,具体内部实现就和单组询问的思想是一样的
然后放下代码就over辣!
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
#define gc getchar()
#define ll long long
#define t(i) edge[i].to
#define lowbit(x) (x&(-x))
#define rp(i,x,y) for(rg ll i=x;i<=y;++i)
#define my(i,x,y) for(rg ll i=x;i>=y;--i)
#define e(i,x) for(rg ll i=head[x];i;i=edge[i].nxt)
const ll N=1e5+10,M=2e5+10,inf=1e9;
ll n,m,head[N],edge_cnt,dfn[N],dfn_cnt,sz[N],tr[N],as[N],fa[N][20],dep[N];
bool output[M];
struct ed{ll to,nxt;}edge[N<<1];
struct node{ll op,fr,to,lca1,lca2,val,id;}opr[M],l[M],r[M];
il ll read()
{
rg char ch=gc;rg ll x=0;rg bool y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il void ad(ll x,ll y){edge[++edge_cnt]=(ed){x,head[y]};head[y]=edge_cnt;}
il void dfs(ll x,ll fat){dep[x]=dep[fat]+1;dfn[x]=++dfn_cnt;sz[x]=1;fa[x][0]=fat;rp(i,1,19)fa[x][i]=fa[fa[x][i-1]][i-1];e(i,x)if(t(i)^fat)dfs(t(i),x),sz[x]+=sz[t(i)];}
il ll lca(ll x,ll y)
{
if(dep[x]<dep[y])swap(x,y);
my(i,19,0)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
my(i,19,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
il void updat(ll x,ll dat){if(!x)return;while(x<=n)tr[x]+=dat,x+=lowbit(x);}
il ll query(ll x){/*printf("x=%lld ",x);*/ll ret=0;while(x)ret+=tr[x],x-=lowbit(x);/*printf("ret=%lld\n",ret);*/return ret;}
il void solv(ll op_l,ll op_r,ll as_l,ll as_r)
{
// printf("op_l=%lld op_r=%lld as_l=%lld as_r=%lld\n",op_l,op_r,as_l,as_r);
if(op_l>op_r)return;if(as_l==as_r){rp(i,op_l,op_r)as[opr[i].id]=as_l;return;}
ll mid=(as_l+as_r)>>1,l_cnt=0,r_cnt=0,bg_cnt=0;
rp(i,op_l,op_r)
{
// printf(" i=%lld op=%lld to=%lld\n",i,opr[i].op,opr[i].to);
if(opr[i].op==3){if(query(dfn[opr[i].to]+sz[opr[i].to]-1)-query(dfn[opr[i].to]-1)==bg_cnt)l[++l_cnt]=opr[i];else r[++r_cnt]=opr[i];continue;}
if(opr[i].op==2)
{
if(opr[i].val<=mid){l[++l_cnt]=opr[i];/*printf("qwq?\n");*/continue;}
else{updat(opr[i].fr,-1);updat(opr[i].to,-1);updat(opr[i].lca1,1);updat(opr[i].lca2,1);--bg_cnt;r[++r_cnt]=opr[i];}
// if(!(opr[i].val<=mid))
// printf("QAQ val=%lld mid=%lld\n",opr[i].val,mid);
continue;
}
if(opr[i].val<=mid){l[++l_cnt]=opr[i];/*printf("qwq???\n");*/continue;}
else{updat(opr[i].fr,1);updat(opr[i].to,1);updat(opr[i].lca1,-1);updat(opr[i].lca2,-1);++bg_cnt;r[++r_cnt]=opr[i];}
// printf("QAQ val=%lld mid=%lld\n",opr[i].val,mid);
}
rp(i,op_l,op_r)
{
if(opr[i].op==2 && opr[i].val>mid){updat(opr[i].fr,1);updat(opr[i].to,1);updat(opr[i].lca1,-1);updat(opr[i].lca2,-1);}
if(opr[i].op==1 && opr[i].val>mid){updat(opr[i].fr,-1);updat(opr[i].to,-1);updat(opr[i].lca1,1);updat(opr[i].lca2,1);}
}
// printf("QAQ l_cnt=%lld\n",l_cnt);
rp(i,1,l_cnt)opr[op_l+i-1]=l[i];rp(i,1,r_cnt)opr[op_l+l_cnt+i-1]=r[i];
solv(op_l,op_l+l_cnt-1,as_l,mid);solv(op_l+l_cnt,op_r,mid+1,as_r);
}
int main()
{
// freopen("wl.in","r",stdin);freopen("wl.out","w",stdout);
n=read();m=read();memset(as,-1,sizeof(as));rp(i,1,n-1){ll x=read(),y=read();ad(x,y);ad(y,x);}dfs(1,0);
rp(i,1,m)
{
// printf("i=%lld\n",i);
ll tmp=read()+1;
if(tmp==1)
{
ll fr_tmp=read(),to_tmp=read(),lca_tmp=lca(fr_tmp,to_tmp),val_tmp=read();opr[i]=(node){1,dfn[fr_tmp],dfn[to_tmp],dfn[lca_tmp],dfn[fa[lca_tmp][0]],val_tmp,i};
}
if(tmp==2){opr[i]=opr[read()];opr[i].op=2;opr[i].id=i;}
if(tmp==3){opr[i].op=3;opr[i].id=i;opr[i].to=read();output[i]=1;}
// printf("i=%lld to=%lld\n",i,opr[i].to);
}
// printf("QAQ?\n");
solv(1,m,-1,inf);rp(i,1,m)if(output[i])printf("%lld\n",as[i]);
return 0;
}