mxqz边分治求卡常
查看原帖
mxqz边分治求卡常
312306
LJ07楼主2022/12/15 21:50

rt,

#include <bits/stdc++.h>
#define ve vector
#define eb emplace_back
#define pb push_back
#define LL long long
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target ("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
namespace FastRead
{
char IC[10000000],*IS,*IT;
#define getchar() (IS==IT&&(IT=IC+fread(IS=IC,1,10000000,stdin)),IS==IT?EOF:*IS++)
int rd()
{
	char c;
	while (!isdigit(c=getchar()));
	int x(c-48);
	while (isdigit(c=getchar())) x=x*10+c-48;
	return x;
}
};
using namespace FastRead;
int main()
{
	int n,l,r,_n;
	n=rd(),l=rd(),r=rd(),_n=n;
	ve<ve<pii>>g(n);
	int L(0),R(40000),mid;
	for (int i(1),u,v,w;i<n;++i) u=rd(),v=rd(),w=rd(),--u,--v,g[u].eb(v,w),g[v].eb(u,w);
	{//Rebuild
		ve<ve<pii>>son(n);
		function<void(int,int)>dfs=[&](int u,int f) 
		{
			for(pii i:g[u])if(i.fi!=f)son[u].eb(i),dfs(i.fi,u);
		};
		dfs(0,0);ve<pii>t;
		for(int i(0);i<_n;++i)
			if(son[i].size()>2)
			{
				son.eb(),son.eb(),swap(son[i],t);
				bool tg(0);
				for(pii j:t)son[_n+(tg^=1)].eb(j);
				son[i].eb(_n++,-1),son[i].eb(_n++,-1);
				t.clear();
			}
		g=ve<ve<pii>>(_n);
		for(int i(0);i<_n;++i) for(pii j:son[i]) g[j.fi].eb(i,j.se),g[i].eb(j);
	}
	int Sz,mn,tmp;bool flg;ve<bool>vis(_n);ve<int>sz(_n);pii ans(0,0);int ansv(-1);
	function<void(int,int&,int&,int&)>Get=[&](int u,int &x,int &y,int &w)
	{
		sz[u]=1,vis[u]=1;
		for(pii i:g[u]) if(!vis[i.fi]) Get(i.fi,x,y,w),sz[u]+=sz[i.fi];
		for(pii i:g[u]) if(!vis[i.fi]) if((tmp=max(Sz-sz[i.fi],sz[i.fi]))<mn) mn=tmp,x=u,y=i.fi,w=i.se;
		vis[u]=0;
	};
	function<void(int,int,int,ve<pii>&)>push=[&](int u,int d,int s,ve<pii>&v)
	{
		vis[u]=1,d+=u<n;
		if (u<n&&d<=r) 
		{
			while (d>=v.size())v.eb(-1e9,-1);v[d]=max(v[d],{s,u});
		}
		for(pii i:g[u]) if(!vis[i.fi]) push(i.fi,d,s+(~i.se?(i.se<mid?-1:1):0),v);
		vis[u]=0;
	};
	pii q[1000005];int fr,bk;
	function<void(int)>calc=[&](int u)
	{
		if(Sz==1) return ;
		int x,y,w,ts;mn=1e9,Get(u,x,y,w);
		ve<pii>vx,vy;ts=~w?(w<mid?-1:1):0;
		vis[y]=1,push(x,-1,0,vx),vis[y]=0;
		vis[x]=1,push(y,-1,0,vy),vis[x]=0;
		{
			int lx(vx.size()),ly(vy.size());
			fr=1,bk=0;
			for (int i(0),j(ly-1);i<lx;++i)
			{
				for (;~j&&i+j+1>=l;--j) 
				{
					while (fr<=bk&&q[bk].se<=vy[j].fi)--bk;
					q[++bk]={j,vy[j].fi};
				}
				while (fr<=bk&&q[fr].fi+i+1>r) ++fr;
				if (fr<=bk&&q[fr].se+vx[i].fi+ts>=0)
				{
					flg=1;
					if (ansv<mid)ansv=mid,ans={vx[i].se,vy[q[fr].fi].se};
				}
			}
		}
		vis[y]=1,Sz=Sz-sz[y],calc(x),vis[y]=0;
		vis[x]=1,Sz=sz[y],calc(y),vis[x]=0;
	};
	while (L<R) (mid=L+R+1>>1,flg=0,Sz=_n,calc(0),flg)?L=mid:R=mid-1;
	cout<<ans.fi+1<<' '<<ans.se+1;
	return 0; 
}                           
2022/12/15 21:50
加载中...