首页 > 其他分享 >Codeforces 1458F - Range Diameter Sum

Codeforces 1458F - Range Diameter Sum

时间:2023-06-29 15:00:46浏览次数:40  
标签:Diameter suf int 1458F mid fa Range MAXN dep

先考虑直径的一些求法:最普遍的想法肯定是从点集中任意一个点开始 DFS 找到距其最远的点,再一遍 DFS 找到距离你找到的那个点最远的点。但是放在这个题肯定是不太行的。因此考虑一种更常用的求法:合并。更直观地说:我们定义树上一个圆 \((x,r)\) 表示距离 \(x\) 点 \(\le r\) 的所有点组成的集合(当然,这里的 \(x\) 不一定是整点,也可能是某条边的中点,\(r\) 也不一定是整数,也可能是某个整数 \(+0.5\),但是把每条边长度乘 \(2\) 后在边上新建一个点则可以避免这些问题)。那么显然一个点集的直径就是覆盖这个点集的最小圆的直径。现在考虑怎么合并两个圆:

  • 如果一个圆完全包含了另一个圆,则返回大圆。
  • 否则,圆心为 \(\text{go}(x_1,x_2,\dfrac{1}{2}(\text{dis}(x_1,x_2)-r_1+r_2))\),半径为 \(\dfrac{1}{2}(\text{dis}(x_1,x_2)+r_1+r_2)\)。

现在考虑怎么计算所有区间的答案。采用枚举右端点维护左端点的做法不可取,因为 modify 方式很复杂。因此考虑另一种求法——分治。预处理 \([l,mid],[mid+1,r]\) 对应的圆,然后枚举左端点,由于随着右端点的增加圆肯定不断变大,所以右端点可以分成三段:\([l,mid]\) 对应的圆完全包含 \([mid+1,r]\) 对应的圆,不存在包含关系和 \([l,mid]\) 对应的圆完全被 \([mid+1,r]\) 对应的圆包含,用 two pointers 维护三段分界点,左右两段显然可以 \(O(1)\) 求得,中间那段相当于要你维护一个点集,支持加入删除一个点并查询点集中所有点到给定点的距离,点分树板子硬上。

时间复杂度 2log。

const int MAXN=2e5;
const int LOG_N=18;
const int MAXD=50;
const int INF=0x3f3f3f3f;
int n,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int fa[MAXN+5][LOG_N+2],dep[MAXN+5];
void dfs0(int x,int f){
	fa[x][0]=f;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f)continue;
		dep[y]=dep[x]+1;dfs0(y,x);
	}
}
int getlca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=LOG_N;~i;i--)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];
	if(x==y)return x;
	for(int i=LOG_N;~i;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int getdis(int x,int y){return dep[x]+dep[y]-2*dep[getlca(x,y)];}
namespace Centroid_Decomposition{
	int siz[MAXN+5],cent,mx[MAXN+5],vis[MAXN+5],dis[MAXD+5][MAXN+5],dfa[MAXN+5],D[MAXN+5];
	void findcent(int x,int f,int totsz){
		siz[x]=1;mx[x]=0;
		for(int e=hd[x];e;e=nxt[e]){
			int y=to[e];if(y==f||vis[y])continue;
			findcent(y,x,totsz);siz[x]+=siz[y];chkmax(mx[x],siz[y]);
		}chkmax(mx[x],totsz-siz[x]);
		if(mx[x]<mx[cent])cent=x;
	}
	void dfs_tree(int x,int f,int D){
		for(int e=hd[x];e;e=nxt[e]){
			int y=to[e];if(y==f||vis[y])continue;
			dis[D][y]=dis[D][x]+1;dfs_tree(y,x,D);
		}
	}
	void divcent(int x){
		vis[x]=1;dfs_tree(x,0,D[x]);
		for(int e=hd[x];e;e=nxt[e]){
			int y=to[e];if(vis[y])continue;cent=0;
			findcent(y,x,siz[y]);dfa[cent]=x;D[cent]=D[x]+1;
			divcent(cent);
		}
	}
	ll mark1[MAXN+5],mark2[MAXN+5],mark3[MAXN+5];
	void ins(int x,int y){
		for(int i=x;i;i=dfa[i]){
			mark1[i]+=y*dis[D[i]][x];mark3[i]+=y;
			if(dfa[i])mark2[i]+=y*dis[D[dfa[i]]][x];
		}
	}
	ll query(int x){
		ll res=0;
		for(int i=x,pre=0;i;pre=i,i=dfa[i])
			res+=mark1[i]-mark2[pre]+1ll*dis[D[i]][x]*(mark3[i]-mark3[pre]);
		return res;
	}
	void init_CD(){
		mx[0]=INF;findcent(1,0,n*2-1);divcent(cent);
//		for(int i=1;i<n*2;i++)printf("%d%c",dfa[i]," \n"[i==n*2-1]);
	}
}
using namespace Centroid_Decomposition;
ll res=0;
int get_kanc(int x,int k){for(int i=LOG_N;~i;i--)if(k>>i&1)x=fa[x][i];return x;}
int go(int x,int y,int k){
	int lc=getlca(x,y);
	if(k<=dep[x]-dep[lc])return get_kanc(x,k);
	else return get_kanc(y,(dep[x]+dep[y]-dep[lc]*2)-k);
}
struct circ{
	int x,r;
	circ(){x=r=0;}
	circ(int _x,int _r){x=_x;r=_r;}
	friend circ operator +(const circ &X,const circ &Y){
		int d=getdis(X.x,Y.x);
		if(X.r>=d+Y.r)return X;
		if(Y.r>=d+X.r)return Y;
		return circ(go(X.x,Y.x,(d-X.r+Y.r)/2),(d+X.r+Y.r)/2);
	}
}pre[MAXN+5],suf[MAXN+5];
void solve(int l,int r){
	if(l==r)return;int mid=l+r>>1;solve(l,mid);solve(mid+1,r);
	pre[mid+1]=circ(mid+1,0);suf[mid]=circ(mid,0);
	for(int i=mid+2;i<=r;i++)pre[i]=pre[i-1]+circ(i,0);
	for(int i=mid-1;i>=l;i--)suf[i]=suf[i+1]+circ(i,0);
	int p1=mid+1,p2=mid+1;ll c1=0,c2=0,s2=0,s3=0;
	for(int i=mid+1;i<=r;i++)s3+=pre[i].r;
	for(int i=mid;i>=l;i--){
		while(p2<=r&&pre[p2].r<getdis(suf[i].x,pre[p2].x)+suf[i].r){
			ins(pre[p2].x,1);c2++;s2+=pre[p2].r;s3-=pre[p2].r;++p2;
		}
		while(p1<p2&&suf[i].r>=getdis(suf[i].x,pre[p1].x)+pre[p1].r){
			ins(pre[p1].x,-1);c2--;s2-=pre[p1].r;c1++;++p1;
		}
		res+=2ll*c1*suf[i].r+2ll*s3+1ll*c2*suf[i].r+s2+query(suf[i].x);
	}
	for(int i=p1;i<p2;i++)ins(pre[i].x,-1);
}
int main(){
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		adde(u,i+n);adde(i+n,u);adde(v,i+n);adde(i+n,v);
	}
	dfs0(1,0);
	for(int i=1;i<=LOG_N;i++)for(int j=1;j<2*n;j++)
		fa[j][i]=fa[fa[j][i-1]][i-1];
	init_CD();solve(1,n);printf("%lld\n",res/2);
	return 0;
}

标签:Diameter,suf,int,1458F,mid,fa,Range,MAXN,dep
From: https://www.cnblogs.com/tzcwk/p/Codeforces-1458F.html

相关文章

  • ARC162E Strange Constraints
    题意给定长度为\(n\)的序列\(A\),求序列\(B\)的个数模\(998244353\),满足以下条件:值域\([1,n]\)。\(i\)的个数不超过\(A_i\)。\(B_i\)的个数不超过\(A_i\)。\(1\len\le500\)。题解发现按照某种顺序去构造是困难的,考虑倒过来,枚举出现次数。如果某个类出现次......
  • VBA对象:Workbooks、Worksheets、Range1
     Workbooks打开工作簿使用VBA可以打开指定位置的目标工作簿,使用Workbooks集合的Open方法。SubWB()'打开工作簿,需要指定完整的路径、名称、后缀名Workbooks.Open"D:\Files\工作簿1.xlsx"EndSub新建工作簿使用Workbooks集合的Add方法创建新的工作簿:S......
  • 悟空派WuKongPi/香橙派orangepi zero全志H3折腾记录(②kernel移植)
    接上一节,这节开始移植内核。 首先获取一下内核源码,这里仍然使用香橙派的源码gitclonehttps://github.com/orangepi-xunlong/linux-orangepi.git 进入kernel根目录并切换到orangepizero使用的分支gitcheckoutremotes/origin/orange-pi-5.4 然后安装编译内核可......
  • AtCoder Regular Contest 162 E Strange Constraints
    洛谷传送门AtCoder传送门完全没有思路。但是其实不难的。设\(d_i\)为\(i\)在\(B\)中的出现次数,题目要求:\(\foralli\in[1,n],d_i\leA_i\);对于位置\(i\),\(d_j\leA_i\)的数\(j\)可以被放到\(B_i\)。考虑按照\(d_i\)从大到小dp。设\(f_{i,j,k}\)......
  • C++使用ranges库解析INI文件
    C++使用ranges库解析INI文件引言C++20引入了<ranges>头文件,C++23对其进行了完善,本文将使用该头文件提供的adaptor编写一个简单的ini解析器。ini文件格式介绍一般的ini文件由section和entry部分,比如[section]key=value;Thisisentry.section和entry均独占一行,其中sectio......
  • ORA-00600[ktfs_upd_range-1]
    ORA-600[ktfs_upd_range-1]DuringTruncateTable(DocID2247478.1)HEATMAPSegmentSizeIsLargeInSYSAUXEvenWhenHeatmap=Off(DocID2024036.1)In12.2.0.1,ORA-600[kpdbSwitchPreRestore:Txn]CrashRACInstances(DocID2583951.1)Thefollowingerror......
  • 悟空派WuKongPi全志H3(香橙派orangepi zero)折腾记录(u-boot移植)
    最近在某宝上看到一个悟空派,仔细一看这不就是香橙派orangepizero吗,不过它的USB是Type-C,于是我买了一块打算折腾一下。 拿到了首先获取一下u-boot源码,因为板子和香橙派orangepizero一样就直接用香橙派的源码了gitclonehttps://github.com/orangepi-xunlong/u-boot-orange......
  • 深入探究for...range语句
    1.引言在Go语言中,我们经常需要对数据集合进行遍历操作。对于数组来说,使用for语句可以很方便地完成遍历。然而,当我们面对其他数据类型,如map、string和channel时,使用普通的for循环无法直接完成遍历。为了更加便捷地遍历这些数据类型,Go语言引入了for...range语句。本文将以数组......
  • ABC237G Range Sort Query
    思路这道题跟P2824的思路是很相似的。首先由于我们只需求一个特定的值在排序后的位置,而原序列又是一个排列,因此我们可以将序列中的所有数分为三种:大于\(X\)的;等于\(X\)的;小于\(X\)的。我们不关心除了\(X\)之外的其他值的具体数字,而只关心其与\(X\)的大小关系,......
  • range 类
    range类型相比常规list或tuple的优势在于一个range对象总是占用固定数量的(较小)内存,不论其所表示的范围有多大(因为它只保存了start,stop和step值,并会根据需要计算具体单项或子范围的值)。#classrange(object):#range(stop)->rangeobject#range(start,stop[,......