首页 > 其他分享 >「题解」Codeforces 825G Tree Queries

「题解」Codeforces 825G Tree Queries

时间:2023-08-23 20:23:57浏览次数:39  
标签:typedef ch int 题解 Tree son 825G siz include

点权转边权,把边权设为两个端点的 \(\min\),然后发现询问 \(x\) 的答案,就是询问 \(x\) 与所有黑点的虚树,边权的 \(\min\) 是多少。假设要判定答案是否 \(\geq k\),那么就是询问 \(x\) 只经过 \(\geq k\) 是否能到达所有黑点,于是想到建立 Kruskal 重构树,那么 \(x\) 与所有黑点的 LCA 的权值即为答案。时间复杂度为 \(\mathcal{O}(n+q\log n)\).

严格比 CF1628E 弱,没救了。。。

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<random>
#include<assert.h>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n'
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n'
#define DE(fmt,...) fprintf(stderr, "Line %d : " fmt "\n",__LINE__,##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<ll,ll>pll;
typedef pair<int,ll>pil;
typedef vector<int>vi;
typedef vector<ll>vll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;
template<typename T>T cmax(T &x, T y){return x=x>y?x:y;}
template<typename T>T cmin(T &x, T y){return x=x<y?x:y;}
template<typename T>
T &read(T &r){
	r=0;bool w=0;char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
	return r=w?-r:r;
}
template<typename T1,typename... T2>
void read(T1 &x,T2& ...y){read(x);read(y...);}
const int N=2000010;
int n,m;
struct Edge{
	int x,y,w;
}e[N];
vi eg[N];
int tot,val[N],fa[N];
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int dep[N],top[N],pa[N],son[N],siz[N];
void dfs1(int x){
	siz[x]=1;
	for(auto v:eg[x]){
		dep[v]=dep[x]+1;pa[v]=x;
		dfs1(v);siz[x]+=siz[v];
		if(siz[v]>siz[son[x]])son[x]=v;
	}
}
void dfs2(int x,int t){
	top[x]=t;
	if(son[x])dfs2(son[x],t);
	for(auto v:eg[x])if(v!=son[x])dfs2(v,v);
}
int LCA(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=pa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
signed main(){
	#ifdef do_while_true
//		assert(freopen("data.in","r",stdin));
//		assert(freopen("data.out","w",stdout));
	#endif
	read(n,m);
	for(int i=1;i<n;i++)read(e[i].x,e[i].y),e[i].w=min(e[i].x,e[i].y);
	sort(e+1,e+n,[&](const Edge &x,const Edge &y){return x.w>y.w;});
	tot=n;
	for(int i=1;i<=n;i++)fa[i]=val[i]=i;
	for(int i=1;i<n;i++){
		int x=e[i].x,y=e[i].y,w=e[i].w;
		x=getfa(x);y=getfa(y);
		++tot;val[tot]=w;
		eg[tot].pb(x);eg[tot].pb(y);
		fa[x]=fa[y]=fa[tot]=tot;
	}
	dfs1(tot);
	dfs2(tot,tot);
	int las=0,t=0;
	while(m--){
		int op,x;read(op,x);
		x=(las+x)%n+1;
		if(op==1){
			if(!t)t=x;
			else t=LCA(t,x);
		}
		else{
			las=val[LCA(t,x)];
			cout<<las<<'\n';
		}
	}
    #ifdef do_while_true
//		cerr<<'\n'<<"Time:"<<1.0*clock()/CLOCKS_PER_SEC*1000<<" ms"<<'\n';
	#endif
	return 0;
}

标签:typedef,ch,int,题解,Tree,son,825G,siz,include
From: https://www.cnblogs.com/do-while-true/p/17652687.html

相关文章

  • 题解 P8816 [CSP-J 2022] 上升点列
    P8816[CSP-J2022]上升点列题目大意给定\(n\)个点,你可以任意添加\(k\)个点,从中选择若干点使得序列中任意相邻两点间的欧几里得距离恰好为\(1\)而且横坐标、纵坐标值均单调不减。换言之,求二维最长上升子序列。solution:很容易想到动态规划,根据最长上升子序列的套路,可以......
  • P1830题解
    思路:利用桶存储轰炸区域,双重循环。在存储轰炸区域时将次数刷新,也就是pos[j][k]=i;。下面是核心代码:for(inti=1;i<=x;i++){ intx1,x2,y1,y2; cin>>x1>>y1>>x2>>y2; for(intj=x1;j<=x2;j++) { for(intk=y1;k<=y2;k++) { vis[j][k]++; pos[j][k]=i; } }......
  • CF1820 & 1819 题解
    Div2A答案取决于_连续段长度,有一些细节,比如什么时候答案要加一减一,以及字符串是单独的^。Div2B首先先把全\(1\)串给特判掉。记将字符串视为首位相接的环的时,最大\(1\)连续段长度为\(x\),答案为\({\lfloor{x+1\over2}\rfloor}({\lfloor{x\over2}\rfloor+1})\)......
  • CF1681E Labyrinth Adventures 题解
    题意有一个\(n\timesn\)的方格图,坐标编号类似平面直角坐标系,左下角为\((1,1)\)。这个方格图被分成了\(n\)层,左下角\((1,1)\)为第一层,随后每层都向外拓展一圈,如下图就是\(n=5\)的时候的情况:层与层之间有墙隔开,但每层都有两个门,分别分布在该层顶部和右侧,门是双向的......
  • h5页面开发常见问题解决方案,助你快速排除问题
    h5页面作为目前广告、宣传以及用户交互的重要工具之一。但是在开发的过程中往往会遇到一些问题,比如兼容性、性能、布局等方面的常见问题。下面,广州名锐讯动将介绍一些h5页面开发常见问题并提供解决方案,帮助您快速排除问题。1.兼容性问题当我们在不同设备和浏览器操作时,h5页面可能......
  • 国标GB28181视频平台EasyGBS国标平台无法正常启动的问题解决方案
    EasyGBS国标视频云服务是基于国标GB/T28181协议的视频能力平台,可实现的视频功能包括:实时监控直播、录像、检索与回看、语音对讲、云存储、告警、平台级联等功能。平台部署简单、可拓展性强,支持将接入的视频流进行全终端、全平台分发,分发的视频流包括RTSP、RTMP、FLV、HLS、WebRTC......
  • Spring Boot通过企业邮箱发邮件被Gmail退回的问题解决方法
    这两天给我们开发的Chrome插件:Youtube中文配音增加了账户注册和登录功能,其中有一步是邮箱验证,所以这边会在SpringBoot后台给用户的邮箱发个验证信息。如果发邮件,之前的文章教程里就有,这里就不说了,着重说说这两天发现所有用Gmail注册的用户都被退件的问题。报错现象先来看看具体......
  • 牛客七夕比赛 题解
    标准的算法竞赛题有下面几个,写这篇博客主要是这个M很有意思,一直没绕过来这个弯如果你有更牛逼的构造方法欢迎交流指导。B构造边长为\(n\)的矩阵,使得每个\(2\times2\)的子矩形的权值和的极差最小两个指针L=1,R=\(n^2\)。将网格黑白染色后按照顺序遍历,黑色填\(R\)......
  • LeetCode 算法题解之 26 进制转换 All In One
    LeetCode算法题解之26进制转换AllInOne26进制转换171.ExcelSheetColumnNumber171.Excel工作表列号functiontitleToNumber(columnTitle:string):number{//如何动态生成字典✅26进制//A-Z->1-26conststrs='ABCDEFGHIJKLMNOPQRSTUVWXYZ';......
  • Google Chrome和ChromeDriver版本号不一致问题解决
    1(base)kaka@KakadeMBPbin%/Applications/Google\Chrome.app/Contents/MacOS/Google\Chrome--version2GoogleChrome116.0.5845.963(base)kaka@KakadeMBPbin%chromedriver--version4ChromeDriver114.0.5735.16(7e1ff058633f5b79b1cd7479aca585ba385......