2025.1.7 做题记录

CF600E

dsu on tree 裸题。

P3899

考虑对 \(a,b\) 的关系分类讨论。对于 \(\operatorname{LCA}(a,b)=b\) 的情况,那么 \(a,b\) 的公共后代一定在 \(a\) 的子树内。即对于所有的 \((a,b)\),其贡献为 \(siz_a-1\)。因为 \(dep_b +k \ge dep_a\),所以 \(dep_b \ge dep_a-k\),每个 \(b\) 的贡献为 \(siz_a-1\)。对于 \(\operatorname{LCA}(a,b)=a\) 的情况,那么 \(a,b\) 的公共后代一定在 \(b\) 子树内。即对于所有 \((a,b)\),其贡献为 \(siz_b-1\)。因为 \(dep_b-k \le dep_a\),所以 \(dep_b \le dep_a+k\),每个 \(b\) 的贡献为 \(siz_b-1\)

那么问题就变成了,求 \(\sum\limits_{\operatorname{LCA}(a,b)=b\land dep_b \ge dep_a-k}^{} siz_a-1 + \sum\limits_{\operatorname{LCA}(a,b)=a\land dep_b \le dep_a+k}^{}siz_b-1\)。前者可以直接计算,因为 \(a\) 已知。后者拍到 DFS 序上就是区间内 \(dep\) 不超过 \(dep_a+k\)\(siz-1\) 的和。可以直接主席树维护。时间复杂度 \(O(n\log n)\)

P3703

染上一个没有染过的点比较麻烦。不如直接染成 \(x\),因为点的编号不同,不肯能有两个 \(x,y (x\ne y)\) 进行操作 \(1\) 得到了相同的值,且仅可能有 \(x\) 到根的路径上存在这个颜色。那么对于求 \(x\)\(y\) 的路径价值,我们就可以树剖维护。对于线段树维护其左端点的颜色,右端点的颜色,这个区间的价值。合并的时候只要相邻的颜色有重复,说明颜色段需要 \(-1\)。对于查询 \(x\) 子树内点到根价值最大值,因为我们相同的颜色肯定是一个点到根路径的前缀。那么当我们进行赋值操作的时候,可以维护出每个颜色的起始位置与终点位置。当我们将 \(1\)\(x\) 的路径覆盖时,一个完全被覆盖的颜色 \(c\) 就会对其子树的颜色产生 \(-1\) 的贡献。由于每个颜色最多被删除和添加共 \(O(n)\) 次,所以暴力维护即可。

我们将两个问题分开考虑。第一个使用树剖维护颜色段,第二个使用普通线段树维护区间最大值。时间复杂度 \(O(n\log^2 n)\)

代码

#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
const int N=2e5+10;
int n,m;
int val[N];
vector<int> e[N];
int mson[N],siz[N],top[N];
int id[N],dfn[N],cnt,dep[N],f[N];
int jump[N][22];
struct Tree1{
	int l,r;
	int cl,cr;
	int val,tag;
}tr[N<<2];
struct Tree2{
	int l,r;
	int tag,mx;
}tr_[N<<2];
int Top[N],Bot[N];
il void up_(int u){
	tr_[u].mx=max(tr_[ls(u)].mx,tr_[rs(u)].mx);
	return ;
}
il void down_(int u){
	if(!tr_[u].tag) return ;
	tr_[ls(u)].tag+=tr_[u].tag,
	tr_[rs(u)].tag+=tr_[u].tag;
	tr_[ls(u)].mx+=tr_[u].tag,
	tr_[rs(u)].mx+=tr_[u].tag;
	return tr_[u].tag=0,void(0);
}
il void build_(int u,int l,int r){
	tr_[u].l=l,tr_[u].r=r;
	if(l==r) return tr_[u].mx=dep[id[l]],void(0);
	int mid=l+r>>1;
	build_(ls(u),l,mid),build_(rs(u),mid+1,r);
	return up_(u),void(0); 
}
il void modify_(int u,int l,int r,int x){
	if(tr_[u].l>=l&&tr_[u].r<=r){
	tr_[u].mx+=x,tr_[u].tag+=x;
	return ;
	}
	down_(u);
	int mid=tr_[u].l+tr_[u].r>>1;
	if(l<=mid) modify_(ls(u),l,r,x);
	if(mid< r) modify_(rs(u),l,r,x);
	return up_(u),void(0);
}
il int query_(int u,int l,int r){
	if(tr_[u].l>=l&&tr_[u].r<=r) return tr_[u].mx;
	down_(u);
	int mid=tr_[u].l+tr_[u].r>>1,mx=0;
	if(l<=mid) mx=max(mx,query_(ls(u),l,r));
	if(mid< r) mx=max(mx,query_(rs(u),l,r));
	return mx;
}
il void up(Tree1 &u,Tree1 x,Tree1 y){
	u.val=x.val+y.val-(x.cr==y.cl);
	u.cl=x.cl,u.cr=y.cr;
	return ;
}
il void down(int u){
	if(!tr[u].tag) return ;
	tr[ls(u)].tag=tr[rs(u)].tag=tr[u].tag;
	tr[ls(u)].cl=tr[ls(u)].cr=tr[u].tag;
	tr[rs(u)].cl=tr[rs(u)].cr=tr[u].tag;
	tr[ls(u)].val=tr[rs(u)].val=1;
	return tr[u].tag=0,void(0);
}
il void build(int u,int l,int r){
	tr[u].l=l,tr[u].r=r;
	if(l==r) return tr[u].cl=tr[u].cr=id[l],tr[u].val=1,void(0);
	int mid=l+r>>1;
	build(ls(u),l,mid),build(rs(u),mid+1,r);
	return up(tr[u],tr[ls(u)],tr[rs(u)]),void(0);
}
il void modify(int u,int l,int r,int x){
	if(tr[u].l>=l&&tr[u].r<=r){
	tr[u].val=1,tr[u].tag=x;
	tr[u].cl=tr[u].cr=x;
	return ;
	}
	down(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) modify(ls(u),l,r,x);
	if(mid< r) modify(rs(u),l,r,x);
	return up(tr[u],tr[ls(u)],tr[rs(u)]),void(0);
}
il Tree1 query(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
	down(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid&&mid< r){
	Tree1 V;
	memset(&V,0,sizeof(V));
	up(V,query(ls(u),l,r),query(rs(u),l,r));
	return V;
	}
	if(l<=mid) return query(ls(u),l,r);
	if(mid< r) return query(rs(u),l,r);
	debug();
}
il int Query_(int u,int x){
	if(tr[u].l==tr[u].r) return tr[u].cl;
	down(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(x<=mid) return Query_(ls(u),x);
	if(mid< x) return Query_(rs(u),x);
}
il void dfs1(int u,int fa){
	int msiz=0;
	jump[u][0]=fa;
	for(re int i=1;i<22;++i) jump[u][i]=jump[jump[u][i-1]][i-1];
	f[u]=fa,dep[u]=dep[fa]+1,mson[u]=-1,siz[u]=1;
	for(auto v:e[u])
	if(v!=fa){
	dfs1(v,u),siz[u]+=siz[v];
	if(msiz<siz[v]) msiz=siz[v],mson[u]=v;
	}
	return ;
}
il void dfs2(int u,int Tp){
	id[++cnt]=u,dfn[u]=cnt;
	top[u]=Tp;
	if(~mson[u]) dfs2(mson[u],Tp);
	for(auto v:e[u])
	if(v!=f[u]&&v!=mson[u]){
	dfs2(v,v);
	}
	return ;
}
il int Up(int u,int S){
	int p=0;
	while(S){
	if(S&1) u=jump[u][p];
	S>>=1,++p;
	}
	return u;
}
il void Modify(int x,int y,int z){
	int lst=0;int To=0;
	int X=x,Y=y,Z=z;Bot[z]=x,Top[z]=1;
	while(x){
	int Col=Query_(1,dfn[x]);
	int Val=query_(1,dfn[x],dfn[x]);
	int id1=top[x],id2=Top[Col];
	if(dep[id1]<dep[id2]){
	modify(1,dfn[id2],dfn[x],z);
	modify_(1,dfn[id2],dfn[id2]+siz[id2]-1,-(Val-1));
	if(lst) modify_(1,dfn[lst],dfn[lst]+siz[lst]-1,(Val-1));
	}
	else{
	modify(1,dfn[id1],dfn[x],z);
	modify_(1,dfn[id1],dfn[id1]+siz[id1]-1,-(Val-1));	
	if(lst) modify_(1,dfn[lst],dfn[lst]+siz[lst]-1,(Val-1));	
	}
	if(x!=Bot[Col]){
	int x_=Up(Bot[Col],dep[Bot[Col]]-dep[x]-1);
	if(x_!=lst) modify_(1,dfn[x_],dfn[x_]+siz[x_]-1,1),To=x_;
	} 
	if(dep[id2]<dep[id1]) x=f[id1],lst=id1;
	else x=f[id2],lst=id2,Top[Col]=To;
	}
	return ;
}
il int Query(int x,int y){
	Tree1 ans1,ans2;
	memset(&ans1,0,sizeof(ans1));
	memset(&ans2,0,sizeof(ans2));
	while(top[x]!=top[y]){
	if(dep[top[x]]>=dep[top[y]]){
	Tree1 ans=query(1,dfn[top[x]],dfn[x]);
	x=f[top[x]];
	up(ans1,ans,ans1);
	}
	else{
	Tree1 ans=query(1,dfn[top[y]],dfn[y]);
	y=f[top[y]];
	up(ans2,ans,ans2);
	}
	} 
	if(dep[x]>=dep[y]) up(ans1,query(1,dfn[y],dfn[x]),ans1);
	if(dep[x]< dep[y]) up(ans2,query(1,dfn[x],dfn[y]),ans2);
	swap(ans1.cl,ans1.cr);
	up(ans2,ans1,ans2);
	return ans2.val;
}
il void solve(){
	n=rd,m=rd;
	for(re int i=1;i< n;++i){
	int u=rd,v=rd;
	e[u].push_back(v),
	e[v].push_back(u);
	}
	dfs1(1,0),top[1]=1,dfs2(1,1);
	build(1,1,n),build_(1,1,n);
	for(re int i=1;i<=n;++i) Top[i]=Bot[i]=i;int Cnt=n;
	while(m--){
	int op=rd;
	if(op==1){
	int x=rd;
	Modify(x,1,++Cnt);
	}
	else if(op==2){
	int x=rd,y=rd;
	printf("%lld\n",Query(x,y));
	}
	else if(op==3){
	int x=rd;
	printf("%lld\n",query_(1,dfn[x],dfn[x]+siz[x]-1));
	}
	}
 return ;
}

CF1280C

考虑对于一条连接 \(u,v\) 的边。如果我们要让路径和最小,显然是不愿意将一对人分在 \(u,v\) 两侧的。那么记 \(siz_u\) 表示 \(u\) 为根的子树大小。\(f_u\) 表示最小代价和。那么有 \(f_u=\sum\limits_{v\in son_u}^{}f_v+w_{u,v}[siz_v ~is ~odd]\)。那么最大价值和同理,我们要让它们尽量经过这条边,有 \(g_u=\sum\limits_{v\in son_u}^{}f_v+w_{u,v}\times \min(n-siz_v,siz_v)\)。时间复杂度 \(O(n)\)

CF1304E

先考虑如果没有加边时的情况。那么很显然的,只要 \(dis_{a,b} \le k\)\(k-dis_{a,b}\) 为偶数就可以了。因为题目不要求走简单路径,而我们折返一次一条边需要经过 \(2\) 次。那么加上 \(x,y\) 这条边同理,我们只需要再计算经过 \(x,y\) 这条边是否可行即可。即 \(dis_{a,x}+1+dis_{y,b} \le k\)\(k-(dis_{a,x}+1+dis_{y,b} )\) 为偶数或 \(dis_{a,y}+1+dis_{x,b} \le k\)\(k-(dis_{a,y}+1+dis_{x,b} )\) 为偶数。时间复杂度 \(O(n\log n)\)

作者:harmis_yz原文地址:https://www.cnblogs.com/harmisyz/p/18656697

%s 个评论

要回复文章请先登录注册