首页 > 其他分享 >CodeForces 1827E Bus Routes

CodeForces 1827E Bus Routes

时间:2023-05-23 18:22:24浏览次数:53  
标签:ps int Bus 1827E dep maxn Routes fst top

洛谷传送门

CF 传送门

比较神奇的题。

定一个非叶子 \(r\) 为根。

显然只用判断两个叶子是否可达。

求出每个叶子向上能一步跳到的深度最浅的点 \(p_i\),那么如果 \(p_i\) 不在一条链上就无解,因为两条路径没有交点。

然后只用判断 \(p_i\) 最深的叶子的 \(p_i\) 能不能一步到达其他叶子即可。

code
// Problem: E. Bus Routes
// Contest: Codeforces - Codeforces Round 873 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1827/E
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 500100;

int n, m, head[maxn], len, deg[maxn], b[maxn];
int fa[maxn], dep[maxn], son[maxn], sz[maxn], top[maxn];
bool vis[maxn];
pii a[maxn];
vector<int> vc[maxn];

struct edge {
	int to, next;
} edges[maxn << 1];

inline void add_edge(int u, int v) {
	edges[++len].to = v;
	edges[len].next = head[u];
	head[u] = len;
}

int dfs(int u, int f, int d) {
	fa[u] = f;
	sz[u] = 1;
	dep[u] = d;
	int maxson = -1;
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (v == f) {
			continue;
		}
		sz[u] += dfs(v, u, d + 1);
		if (sz[v] > maxson) {
			son[u] = v;
			maxson = sz[v];
		}
	}
	return sz[u];
}

void dfs2(int u, int tp) {
	top[u] = tp;
	vis[u] = 1;
	if (!son[u]) {
		return;
	}
	dfs2(son[u], tp);
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (!vis[v]) {
			dfs2(v, v);
		}
	}
}

inline int qlca(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) {
			swap(x, y);
		}
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) {
		swap(x, y);
	}
	return x;
}

void solve() {
	len = 0;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		head[i] = deg[i] = son[i] = 0;
		vector<int>().swap(vc[i]);
		vis[i] = 0;
	}
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		add_edge(u, v);
		add_edge(v, u);
		++deg[u];
		++deg[v];
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &a[i].fst, &a[i].scd);
		vc[a[i].fst].pb(a[i].scd);
		vc[a[i].scd].pb(a[i].fst);
	}
	if (n == 2) {
		for (int i = 1; i <= m; ++i) {
			if (a[i].fst != a[i].scd) {
				puts("YES");
				return;
			}
		}
		puts("NO\n1 2");
		return;
	}
	int r = -1;
	for (int i = 1; i <= n; ++i) {
		if (deg[i] > 1) {
			r = i;
			break;
		}
	}
	dfs(r, -1, 1);
	dfs2(r, r);
	int p = -1, q = -1, mx = -1e9;
	vector<pii> ps;
	for (int u = 1; u <= n; ++u) {
		if (deg[u] != 1) {
			continue;
		}
		int k = -1, mn = 1e9;
		if (vc[u].empty()) {
			printf("NO\n%d %d\n", u, r);
			return;
		}
		for (int v : vc[u]) {
			int w = qlca(u, v);
			if (dep[w] < mn) {
				mn = dep[w];
				k = w;
			}
		}
		b[u] = k;
		ps.pb(k, u);
		if (dep[k] > mx) {
			mx = dep[k];
			p = k;
			q = u;
		}
	}
	sort(ps.begin(), ps.end(), [&](pii x, pii y) {
		return dep[x.fst] < dep[y.fst];
	});
	for (int i = 0; i + 1 < (int)ps.size(); ++i) {
		if (qlca(ps[i].fst, ps[i + 1].fst) != ps[i].fst) {
			printf("NO\n%d %d\n", ps[i].scd, ps[i + 1].scd);
			return;
		}
	}
	for (int u = 1; u <= n; ++u) {
		if (deg[u] != 1 || u == q) {
			continue;
		}
		bool flag = 1;
		for (int v : vc[u]) {
			if (qlca(v, p) == p || qlca(u, p) == p) {
				flag = 0;
				break;
			}
		}
		if (flag) {
			printf("NO\n%d %d\n", u, q);
			return;
		}
	}
	puts("YES");
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:ps,int,Bus,1827E,dep,maxn,Routes,fst,top
From: https://www.cnblogs.com/zltzlt-blog/p/17426057.html

相关文章

  • 我的第一个项目(十三) :组件间传值的一些方案(vuex,eventbus,localStorage)
    好家伙, 先说一下我的需求,我要组件间传值 1.eventBus前端兄弟组件传值eventbus无法使用不报错也不触发,就很奇怪//eventBus.jsimportVuefrom"vue";exportdefaultnewVue();//Mylogin.vue<buttontype="button"class="btnbtn-primary"@click="login&quo......
  • BUS Hount 抓包如何设置抓包显示时间等内容——设置显示栏中设置
    抓包设置选择“Settings”在“Limits”中设置最大数据包速率,和最大包长;在“ColumntoDisplay”中设置显示,这里我们设置显示数据包长度、输入输出、数据(hex格式)、描述、时间差、时间、日期。......
  • freemodbus移植进STM32(包含HAL库和标准库两种方法)
    freemodbus移植基于freemodbus1.6使用HAL库软件:stm32cubemxstm32cubeide后续会更新标准库的移植。以及rtos下的移植(尽量)下载freemodbus1.6这个获取方法网上到处都是,不细说了。cubemx新建工程新建工程只列出了与移植freemodbus相关的设置这里我使用的是485通信,所以......
  • 深入解析buffer busy waits
    在写一个培训ppt的时候,为了深入理解buffebusywaits这个等待事件,做了一个仔细的测试,对大家也有帮助,经过测试,发现我个人以前的认识都有一点问题。大家一起探讨!1.创建测试表www.killdb.com>connroger/rogerConnected.www.killdb.com>create......
  • 工程监测无线中继采集仪的参数读写MODBUS协议
    工程监测无线中继采集仪的参数读写MODBUS协议 无线中继采集仪支持基于地址的MODBUS协议、自定义的AAB/B协议以及字符串指令集协议,使用这些通讯协议可对寄存器(参数)进行访问。MODBUS协议无线中继采集仪支持MODBUS的03、04、06指令码。(1)03(0x03)/03(0x04)指令码:读取......
  • delphi实现modbus通信
    -------------------------------------------------------------基础单元----start-----------------------------------------------------------------------------{********************************************************************}{*单元名称:UntM......
  • dbus -qt
    xml   D-Bus等价类型   Qt数据类型as   Arrayof[string]   QList<QString>a{sv}   dictofstring   QVariantMapa{sa{sv}}   dictofobjectpath   QMap<QString,QVariantMap>a{oa{sa{sv}}}   dictofobjectpath   QMap<QDBusObje......
  • HTB靶场之Busqueda
    准备:攻击机:虚拟机kali和win10(常规操作就直接用本机win10来操作了)。靶机:Inject,htb网站:https://www.hackthebox.com/,靶机地址:https://app.hackthebox.com/machines/Busqueda。知识点:命令执行、敏感信息发现。备注:这个说难也难说简单也是很简单,如果要通过命令执行来进行shell反弹......
  • centos7 中安装 busco
     001、系统[root@PC1software]#cat/etc/redhat-releaseCentOSLinuxrelease7.9.2009(Core) 002、python版本[root@PC1software]#python3--versionPython3.11.3 003、gcc版本[root@PC1software]#gcc--versiongcc(GCC)4.8.520150623(RedHat......
  • 【Azure 服务总线】如何批量删除Azure Service Bus中的Topics(数量较多,需要过滤后批量
    问题描述AzureServiceBus的门户操作页面上,是否可以批量删除其中的Topics呢? 问题解答AzureServiceBus门户或ServiceBusExplorer工具没有提供批量删除Topic的方法。但是可以自己写脚本删除,并且可以在删除的时候自定义过滤条件。以Python举例:第一步:在本地安装PythonServiceB......