题目链接:Codeforces 455C Civilization
题目大意:给定N,M和Q,N表示有N个城市,M条已经修好的路,修好的路是不能改变的,然后是Q次操作,操作分为两种,一种是查询城市x所在的联通集合中,最长的路为多长。二是连接两个联通集合,采用联通之后最长路最短的方案。
解题思路:因为一开时的图是不可以改变的,所以一开始用dfs处理出各个联通集合,并且记录住最大值,然后就是Q次操作,用并查集维护,注意因为联通的时候要采用最长路径最短的方案,所以s的转移方程变为s = max(s, (s+1)/2 + (s0+1)/2 + 1)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 3 * 1e5 + 5;
int N, M, Q, f[maxn], s[maxn];
int root, ans, rec;
vector<int> g[maxn];
int getfar(int x) {
return f[x] == x ? x : f[x] = getfar(f[x]);
}
void link (int u, int v) {
int x = getfar(u);
int y = getfar(v);
if (x == y)
return;
if (s[x] < s[y])
swap(s[x], s[y]);
f[y] = x;
s[x] = max(s[x], (s[x] + 1) / 2 + (s[y] + 1) / 2 + 1);
}
void dfs (int u, int p, int d) {
f[u] = root;
if (d > ans) {
ans = d;
rec = u;
}
for (int i = 0; i < g[u].size(); i++) {
if (g[u][i] != p)
dfs(g[u][i], u, d+1);
}
}
int main () {
int type, u, v;
scanf("%d%d%d", &N, &M, &Q);
for (int i = 1; i <= N; i++) {
f[i] = i;
g[i].clear();
}
for (int i = 0; i < M; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= N; i++) {
if (f[i] == i) {
root = rec = i;
ans = -1;
dfs(i, 0, 0);
ans = -1;
dfs(rec, 0, 0);
s[i] = ans;
}
}
for (int i = 0; i < Q; i++) {
scanf("%d", &type);
if (type == 1) {
scanf("%d", &u);
v = getfar(u);
printf("%d\n", s[v]);
} else {
scanf("%d%d", &u, &v);
link(u, v);
}
}
return 0;
}
分享到:
相关推荐
Codeforces Round #620 (Div. 2) [codeforces 1304A] Two Rabbits 整除+模 总目录详见https://blog.csdn.net/mrcrack/article/details/103564004 在线测评地址https://codeforces.ml/contest/1304/problem/A ...
解决问题(문제해결) ACM-ICPC凭证,BOJ,CodeForces,Codewars,SCPC,摇动,TopCoder凭证
【并查集】Codeforces 566D Restructuring Company题面在这里对于本题,只需要再维护一个并查集表示i所在联通块的最右位置因为相邻
题目大意:给出一个数列 a ,求出 题目分析:如果暴力的话显然时间复杂度是 n * n 的,我们应该想办法去优化,比赛的时候想用线段树,但是不会在维护异或的前提下区间加法,也想过用矩阵维护,但丝毫没什么用呀,...
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
# sublime-plugin-for-codeforces 自定义构建,用于从 codeforces 获取测试用例并检查程序是否正确。 平台:GNU/Linux 语言:Python2.7.9 描述:这个程序从 codeforces 中获取测试用例,并告诉你程序的输出是否与...
codeforces编程网站预测分数插件
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
codeForces C ++中的Code Force解决方案
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<=st[y]<=ed[y]<=ed[x]. 即...
Codeforces round 678 division 2 codes
Codeforces扩展包 是否曾经想让Codeforce拥有方便的快捷键,自动更新排行榜,可以按需隐藏/显示的问题标签,更好的站点导航,深色主题或以上所有功能? 这些和更多功能可以在Codeforces ++中获得! 该扩展是开源的,...