自动搬运

查看原文

来自洛谷，原作者为

	一粒夸克 **

搬运于2025-08-24 22:16:13，当前版本为作者最后更新于2022-01-15 11:42:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

既然没有题解那我就发一篇吧

这题是三道题的结合体：CF464E The Classic Problem、洛谷 P4178 Tree、S2oj 55. 小芈

可以发现，由于图中只有 $n-1$ 条边，若边权为 $n^z$ ，相加时是不会发生进位的。

因此我们比较两条路径时，只需依次比较每个数字出现的个数即可。

可以用主席树维护哈希值，把单次比较的复杂度优化到 $O(\log n)$。

考虑二分答案。

我们先进行一次边分治，预处理出所有的“半条路径”，然后排序。

这样一来，对于左边的一条路径，右边和它相加后权值在当前区间内的路径会在一个区间内。

因此，我们可以对于每个左边的路径维护可以和它匹配的右路径的区间，不必维护所有的路径对，并且可以双指针在 $O(n\log^2n)$ （含 $O(\log n)$ 的比较和 $O(\log\ n)$ 的边分治）的时间复杂度内算出一条路径在当前路径集合中的排名。

考虑到边权很大，而路径只有 $n^2$ 条，我们可以去二分路径。

由于我们不好直接找出当前路径集合的中位数，我们可以随机选出一条路径来当作中位数。

因为不同路径的长度有可能相同，我们不能等集合大小为 1 了再停止二分，我们可以人为设定一个二分次数，50~60 最好。

总时间复杂度 $O(n\log^3n)$

code：

目前同时是洛谷和 LOJ 的 rank1

#include<bits/stdc++.h>
using namespace std;
int n,m,lim;long long k;
vector<int> rt1[400005],rt2[400005];
namespace Main{
	int le[10000005],ri[10000005],siz[10000005],cnt;
	unsigned long long tree[10000005],val[100005];
	int insert(int loc,int y,int l=1,int r=n){
		if(loc<l||loc>r)return y;
		int i=++cnt;tree[i]=tree[y]+val[loc];siz[i]=siz[y]+1;
		if(l!=r){
	    	int mid=(l+r)>>1;
    		le[i]=insert(loc,le[y],l,mid);ri[i]=insert(loc,ri[y],mid+1,r);
 		}
		return i;
	}
	inline bool cmp(int a,int b,int c,int d){
		int l=1,r=n;
		while(l!=r){
			int mid=(l+r)>>1;
			if(tree[ri[a]]+tree[ri[b]]!=tree[ri[c]]+tree[ri[d]]){
				l=mid+1;
				a=ri[a];b=ri[b];c=ri[c];d=ri[d];
			}else {
				r=mid;
				a=le[a];b=le[b];c=le[c];d=le[d];
			}
		}
		return siz[a]+siz[b]<siz[c]+siz[d];
	}
	inline bool ccmp(int x,int y){
		return cmp(x,0,y,0);
	}
	vector<int> L[400005],R[400005],pos[400005];
	struct node{
		int x,y;
		node(int _x,int _y){
			x=_x;y=_y;
		}
		inline bool operator <(const node &b)const{
			return cmp(x,y,b.x,b.y);
		}
	};
	long long ans,base=1;
	const long long md=1e9+7;
	void Get(int x,int y,int l=1,int r=n){
		if(l==r){
			base=base*n%md;ans=(ans+(siz[x]+siz[y])*base)%md;
			return ;
		}
		int mid=(l+r)>>1;
		Get(le[x],le[y],l,mid);Get(ri[x],ri[y],mid+1,r);
	}
	inline void main(){
		long long all=0;
		for(int i=1;i<=lim;i++){
			L[i].resize(rt1[i].size());R[i].resize(rt1[i].size());pos[i].resize(rt1[i].size());
			for(auto &it:R[i])it=rt2[i].size()-1;all+=1ll*rt1[i].size()*rt2[i].size();
		}
		node mid(0,0);
		for(int t=1;t<=60;t++){
			long long rk=abs(1ll*rand()*rand()+rand())%all+1;
			for(int i=1;rk&&i<=lim;i++){
				for(int j=0;j<rt1[i].size();j++){
					int tmp=R[i][j]-L[i][j]+1;
					if(tmp>=rk){
						mid=node(rt1[i][j],rt2[i][L[i][j]+rk-1]);
						rk=0;break;
					}else rk-=tmp;
				}
			}
			long long tmp=0;
			for(int i=1;i<=lim;i++){
				int r=rt2[i].size()-1;
				for(int j=0;j<rt1[i].size();j++){
					r=min(r,R[i][j]);
					while(r>=L[i][j]&&mid<node(rt1[i][j],rt2[i][r]))r--;
					pos[i][j]=r;tmp+=r-L[i][j]+1;
				}
			}
			if(k==tmp)break;
			else if(k<tmp){
				all=tmp;
				for(int i=1;i<=lim;i++){
					for(int j=0;j<rt1[i].size();j++)R[i][j]=pos[i][j];
				}
			}else {
				k-=tmp;all-=tmp;
				for(int i=1;i<=lim;i++){
					for(int j=0;j<rt1[i].size();j++)L[i][j]=pos[i][j]+1;
				}
			}
		}
		Get(mid.x,mid.y);
		printf("%lld",ans);
	}
}
namespace Init{
	int ver[400005],ne[400005],head[200005],cnt=1,val[400005];
	inline void link(int x,int y,int v){
		ver[++cnt]=y;
     	ne[cnt]=head[x];
		head[x]=cnt;val[cnt]=v;
	}
	vector<pair<int,int> > son[100005];
	int las[100005];
	void init(int x,int fi){
		for(auto it:son[x]){
			int u=it.first;if(u==fi)continue;
			init(u,x);
			if(!las[x])link(x,u,it.second),link(u,x,it.second),las[x]=x;
			else {
				link(las[x],++m,0);link(m,las[x],0);las[x]=m;
				link(las[x],u,it.second);link(u,las[x],it.second);
			}
		}
	}
	int siz[200005],mxp[200005],root;
	bool vis[400005];
	void findrt(int x,int fi,int tot){
		siz[x]=1;
		for(int i=head[x];i;i=ne[i]){
			int u=ver[i];if(vis[i]||u==fi)continue;
			findrt(u,x,tot);siz[x]+=siz[u];mxp[i>>1]=max(tot-siz[u],siz[u]);
			if(mxp[root]>mxp[i>>1])root=(i>>1);
		}
	}
	int rt[200005];
	vector<int> vec;
	void dfs(int x,int fi){
		if(x<=n)vec.push_back(rt[x]);
		siz[x]=1;
		for(int i=head[x];i;i=ne[i]){
			int u=ver[i];
			if(vis[i]||u==fi)continue;
			rt[u]=Main::insert(val[i],rt[x]);
			dfs(u,x);siz[x]+=siz[u];
		}
	}
	void solve(int x,int tot){
		mxp[root=0]=m;findrt(x,x,tot);
		if(!root)return ;vis[root<<1]=vis[root<<1|1]=1;
		int L=ver[root<<1],R=ver[root<<1|1];++lim;
		rt[L]=0;vec.clear();dfs(L,R);
		sort(vec.begin(),vec.end(),Main::ccmp);swap(rt1[lim],vec);
		rt[R]=Main::insert(val[root<<1],0);vec.clear();dfs(R,L);
		sort(vec.begin(),vec.end(),Main::ccmp);swap(rt2[lim],vec);
		solve(L,siz[L]);solve(R,siz[R]);
	}
	inline void main(){
		for(int i=1;i<=n;i++)Main::val[i]=1ll*rand()*rand()*rand()+1ll*rand()*rand()+rand();
		for(int i=1;i<n;i++){
			int x,y,v;
			scanf("%d%d%d",&x,&y,&v);
			son[x].push_back(make_pair(y,v));
			son[y].push_back(make_pair(x,v));
		}m=n;
		init(1,1);solve(1,m);
	}
}
int main(){
	scanf("%d%lld",&n,&k);
	Init::main();
	Main::main();

	return 0;
}