hihoCoder #1167 : 高等理论计算机科学(LCA)

Description:

少女幽香这几天正在学习高等理论计算机科学,然而她什么也没有学会,非常痛苦。所以她出去晃了一晃,做起了一些没什么意义的事情来放松自己。
门前有一颗n个节点树,幽香发现这个树上有n个小精灵。然而这些小精灵都比较害羞,只会在一条特定的路径上活动。第i个小精灵会在ai到bi的路径上活动。
两个小精灵是朋友,当且仅当它们的路径是有公共点的。
于是幽香想要知道,有多少对小精灵a和b,a和b是朋友呢?其中a不等于b,a,b和b,a看做一对。

Input:

第一行n和P (1 <= n, P <=100000),表示树的大小和小精灵的个数。树的节点从1到n标号。
接下来n-1行,每行两个数a,b,表示a到b之间有一条边。
接下来P行,第i行两个数ai,bi,表示小精灵i的活动范围是ai到bi,其中ai不等于bi。

Output:

一行答案,表示对数。

Sample Input:

6 3
1 2
2 3
2 4
4 5
4 6
1 3
1 5
5 6

Sample Output:

2

题目链接

对于小精灵的活动范围离线查询LCA,统计每个LCA节点i的LCA数量Cnt[i],之后Dfs算出根节点到节点i的LCA数量值之和Sum[i],计算每个小精灵活动范围路径上的其他小精灵活动范围LCA节点的个数(两端点a,b之间的个数就是Sum[a]+Sum[b]-2×Sum[LCA(a,b)]),最后由于某些节点不止是一条路径的LCA,需要对最终答案乘以C(2,Cnt)。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

struct Edge {
	int V, Next;
};

struct Query {
	int Q, Next;
	int Index;
};

struct Input {
	int U, V;
};

int N, P;
int Pre[maxn << 2];
Edge edges[maxn << 2];
int Head[maxn];
int Tot;
Query querys[maxn << 2];
int QHead[maxn];
int QTot;
int Vis[maxn];
int Ancestor[maxn];
int Answer[maxn];
int Sum[maxn];
int Cnt[maxn];
Input inputs[maxn];
long long Ans;

int Find(int X) {
	int R = X;
	while (Pre[R] != -1) {
		R = Pre[R];
	}
	return R;
}

void Join(int U, int V) {
	int RU = Find(U), RV = Find(V);
	if (RU != RV) {
		Pre[RU] = RV;
	}
}

void Init() {
	Tot = 0;
	memset(Head, -1, sizeof(Head));
	QTot = 0;
	memset(QHead, -1, sizeof(QHead));
	memset(Vis, false, sizeof(Vis));
	memset(Pre, -1, sizeof(Pre));
	memset(Ancestor, 0, sizeof(Ancestor));
	memset(Sum, 0, sizeof(Sum));
	memset(Cnt, 0, sizeof(Cnt));
}

void Addedge(int U, int V) {
	edges[Tot] = Edge {V, Head[U]};
	Head[U] = Tot++;
}

void AddQuery(int U, int V, int Index) {
	querys[QTot] = Query {V, QHead[U], Index};
	QHead[U] = QTot++;
	querys[QTot] = Query {U, QHead[V], Index};
	QHead[V] = QTot++;
}

void Tarjan(int Node) {
	Ancestor[Node] = Node;
	Vis[Node] = true;
	for (int i = Head[Node]; ~i; i = edges[i].Next) {
		if (Vis[edges[i].V]) {
			continue;
		}
		Tarjan(edges[i].V);
		Join(Node, edges[i].V);
		Ancestor[Find(Node)] = Node;
	}
	for (int i = QHead[Node]; ~i; i = querys[i].Next) {
		if (Vis[querys[i].Q]) {
			Answer[querys[i].Index] = Ancestor[Find(querys[i].Q)];
		}
	}
}

void Dfs(int Cur, int Parent) {
	Vis[Cur] = true;
	Sum[Cur] = Sum[Parent] + Cnt[Cur];
	for (int i = Head[Cur]; ~i; i = edges[i].Next) {
		if (Vis[edges[i].V]) {
			continue;
		}
		Dfs(edges[i].V, Cur);
	}
}

int main(int argc, char *argv[]) {
	Init();
	scanf("%d%d", &N, &P);
	for (int i = 1, U, V; i < N; ++i) {
		scanf("%d%d", &U, &V);
		Addedge(U, V);
	}
	for (int i = 1; i <= P; ++i) {
		scanf("%d%d", &inputs[i].U, &inputs[i].V);
		AddQuery(inputs[i].U, inputs[i].V, i);
	}
	Tarjan(1);
	for (int i = 1; i <= P; ++i) {
		Cnt[Answer[i]]++;
	}
	memset(Vis, false, sizeof(Vis));
	Dfs(1, 0);
	Ans = 0;
	for (int i = 1; i <= P; ++i) {
		Ans += Sum[inputs[i].U] + Sum[inputs[i].V] - 2 * Sum[Answer[i]];
	}
	for (int i = 1; i <= N; ++i) {
		Ans += 1LL * Cnt[i] * (Cnt[i] - 1) / 2;
	}
	printf("%lld\n", Ans);
    return 0;
}
全部评论

相关推荐

02-22 20:28
重庆大学 Java
程序员牛肉:首先不要焦虑,你肯定是有希望的。 首先我觉得你得好好想一想自己想要什么。找不到开发岗就一定是失败的吗?那开发岗的35岁危机怎么说?因此无论是找工作还是考公我觉得你都需要慎重的想一想。但你一定要避开这样一个误区:“我是因为找不到工作所以不得不选择考公”。 千万不要这么想。你这个学历挺好的了,因此你投后端岗肯定是有面试机会的。有多少人简历写的再牛逼,直接连机筛简历都过不去有啥用?因此你先保持自信一点。 以你现在的水平的话,其实如果想要找到暑期实习就两个月:一个月做项目+深挖,并且不断的背八股。只要自己辛苦一点,五月份之前肯定是可以找到暑期实习的,你有点太过于高看大家之间的技术差距了。不要焦虑不要焦虑。 除此之外说回你这个简历内容的话,基本可以全丢了。如果想做后端,先踏踏实实做两个项目再说+背八股再说。如果想考公,那就直接备战考公。 但是但是就像我前面说的:你考公的理由可以是因为想追求稳定,想追求轻松。但唯独不能是因为觉得自己找不到工作。不能这么小瞧自己和自己的学历。
点赞 评论 收藏
分享
1.&nbsp;事件概述3月10日下午,华为在“心声社区”发布长达6500字通报,曝光72名正式员工及19名非雇员在非雇员招聘中存在徇私舞弊行为,多人出卖公司信息资产获利,引发热议。-&nbsp;“非雇员”一般指华为OD员工,与人力服务公司签劳动合同,以派遣方式到华为工作,薪资待遇与华为内部员工基本一致,可通过考核转正。2.&nbsp;相关传言与真相华为相关人士称暂无官方回应,很多传言细节不准确。&nbsp;华为成都研究所员工透露,此次通报主要涉及成都研究所的数据存储部门,整个数据存储业务约100余人,此次明文通报除名辞退或通报批评的有62名,“很多部门基本全开除”&nbsp;。网传任正非亲赴成都、封楼抓人等消息不实。早在2024年年中,就有...
七安有出处嘛:省流:任正非亲赴成都等消息不实,2024 年年中就有人举报了;涉及36名违规当事人,其中有13人被除名;10人有主动申报情节或情节较严重的,予以辞退处理;另有13人被劝退、个人职级降3等。另外还有26名相关管理责任人作为直接或间接管理者,被处以个人职级降6等,冻结个人涨薪、职级晋升、干部向上任命,冻结期6—12个月不等;若下属违规偶发,则仅通报批评。并没有释放100HC😂😂😂
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务