并不对劲的loj2050:p3248:[HNOI2016]树

题目大意

有一棵\(n\)个点的树，根为1号点，称它为“模板树”。
有一棵初始和模板树相同的树，称它为“当前树”。
对“当前树”有\(m\)次操作，每次操作给出两个数\(x,y\)表示将模板树中\(x\)及其子树复制下来并粘贴到模板树，该子树的根与点\(y\)连边，假设操作前“当前树”有\(a\)个点，“模板树”中\(x\)的子树大小为\(b\)，则粘贴上去的\(b\)个点的标号按这棵子树在“模板树”中的标号从小到大的顺序依次标为\(a+1,a+2,...,a+b\)。
\(m\)次操作后，有\(q\)次询问，每次问“当前树”上两点间的距离。
\(n,m,q\leq 10^5;\)

题解

建另一棵树：对于每次操作，粘贴过去的子树的根向点\(y\)所在的树的“根”连边（如果点\(y\)是之前的某一次粘贴过去的点，那么它的“根”是粘贴过去时子树的根，而不是整棵树的根）。
询问两点距离时分类讨论它们是不是同一次粘贴过去的。如果是就直接在模板树上求，如果不是就让它们分别走到和它们同一次粘贴过去的子树的根，再在新树中求LCA。

代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define maxn 100007
#define maxnd 2000007
#define LL long long
#define pll pair
#define fi first
#define se second
#define mp make_pair
#define ls ch[u][0]
#define rs ch[u][1]
#define mi ((l+r)>>1)
using namespace std;
LL read()
{
	LL 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;
}
void write(LL x)
{
	if(x==0){putchar('0'),putchar('\n');return;}
	int f=0;char ch[20];
	if(x<0)putchar('-'),x=-x;
	while(x)ch[++f]=x%10+'0',x/=10;
	while(f)putchar(ch[f--]);
	putchar('\n');
	return;
}
struct nd{LL fa,start;int bac;}ad[maxn];
LL nowsiz,qu[maxn],qv[maxn],dis[maxn][20];
vectorqx[maxn];
int rt[maxn],ch[maxnd][2],num[maxnd],siz[maxn],cntnd,cntad,cnte,dep2[maxn];
int n,m,q,fir[maxn],nxt[maxn<<1],v[maxn<<1],st[20][maxn<<1],tim,dfn[maxn],lg[maxn<<1],dep[maxn],anc[maxn][20];
mapto;
void ade(int u1,int v1){v[cnte]=v1,nxt[cnte]=fir[u1],fir[u1]=cnte++;}
void getdfn(int u)
{
	st[0][++tim]=u,dfn[u]=tim,siz[u]=1;
	view(u,k)if(!dep[v[k]]&&v[k]!=1){dep[v[k]]=dep[u]+1,getdfn(v[k]),siz[u]+=siz[v[k]],st[0][++tim]=u;}
}
inline int lca(int x,int y)
{
	x=dfn[x],y=dfn[y];if(x>y)swap(x,y);
	int len=y-x+1;return dep[st[lg[len]][x]]>1;
		if(ad[mid].start<=x)res=max(res,mid),L=mid+1;
		else R=mid-1;
	}
	return res;
}
inline void pu(int u){num[u]=0;if(ls)num[u]+=num[ls];if(rs)num[u]+=num[rs];return;}
int build(int l,int r,int x)
{
	int u=++cntnd;
	if(x<=l&&r<=x){num[u]=1;return u;}
	if(x<=mi)ls=build(l,mi,x);
	else rs=build(mi+1,r,x);
	num[u]=1;return u;
}
int merge(int u,int ub,int l,int r)
{
	if(!u||!ub){return u|ub;}
	ls=merge(ls,ch[ub][0],l,mi);
	rs=merge(rs,ch[ub][1],mi+1,r);
	pu(u);return u;
}
int ask(int u,int l,int r,int x)
{
	if(l==r)return l;
	if(!ls||num[ls]dep[u]){getto(v[k]),rt[u]=merge(rt[u],rt[v[k]],1,n);}
	int li=qx[u].size()-1;
	rep(i,0,li){to[qx[u][i].fi]=ask(rt[u],1,n,qx[u][i].se);}
}
int main()
{
	n=read(),m=read(),q=read();
	rep(i,1,n)fir[i]=-1;
	rep(i,2,n){int x=read(),y=read();ade(x,y),ade(y,x);}
	getdfn(1);lg[0]=-1;
	rep(i,1,tim)lg[i]=lg[i>>1]+1;
	rep(i,1,lg[tim])for(int j=1;j+(1<dep2[idy])
			{
				if(x&&to[x]!=ad[idx].bac)ans+=Dis(to[x],ad[idx].bac);
				ans+=dis[idx][i],idx=anc[idx][i],x=0;
			}
			if(anc[idx][0]==idy)
			{
				if(x&&to[x]!=ad[idx].bac)ans+=Dis(to[x],ad[idx].bac);x=0;
				ans+=Dis(to[ad[idx].fa],to[y])+1;
			}
			else 
			{
				if(dep2[idx]>dep2[idy])
				{
					if(x&&to[x]!=ad[idx].bac)ans+=Dis(to[x],ad[idx].bac);
					ans+=dis[idx][0],idx=anc[idx][0],x=0;
				}
				dwn(i,19,0)if(anc[idx][i]&&anc[idy][i]&&anc[idx][i]!=anc[idy][i])
				{
					if(x&&to[x]!=ad[idx].bac)ans+=Dis(to[x],ad[idx].bac);
					if(y&&to[y]!=ad[idy].bac)ans+=Dis(to[y],ad[idy].bac);
					ans+=dis[idx][i]+dis[idy][i],idx=anc[idx][i],idy=anc[idy][i];x=0,y=0;
				}
				if(x&&to[x]!=ad[idx].bac)ans+=Dis(to[x],ad[idx].bac);
				if(y&&to[y]!=ad[idy].bac)ans+=Dis(to[y],ad[idy].bac);
				ans+=Dis(to[ad[idx].fa],to[ad[idy].fa])+2;
			}
		}
		write(ans);
	}
	return 0;
}
二分+题目来源：loj+题目来源：洛谷倍增

相关

LCA/在线(倍增)离线(Tarjan)

牛客练习赛91（并查集+二维偏序+二分）

数据结构与算法之PHP查找算法（二分查找）

二分查找模板（准确找定值）

浅谈二分的边界问题

算法之二分法

The 2021 CCPC Guilin Onsite【A,I,G(二分),D（思维+构造）,E（最短路】

b_lc_实现除法（倍增思想）

leetcode-二分查找相关

二分查找算法细节详解

c_mt_找有k个数小于自己的数（二分->复杂化 / 排序简化）

二分搜索的变形

标签