←_←

题目链接思路用可持久化数组维护历史版本的 fa 父亲数组和 dep 树深度数组，以树深按秩合并。代码#include <stdio.h>const int maxn = 2e5+5;int n, m;struct Node{ int l, r, val;}h[maxn*80];int cnt, rootfa[maxn], rootdep[maxn], t...

题目链接题意给一张无向图，多次查询两点，求两点之间最小瓶颈路的权值。思路最小生成树+LCA是一种，下面讲另种方法通过限制树的高度暴力LCA求解。首先可以用Kruskal求最小生成树，那么任意两连通的点最小瓶颈路都会在生成树上。在Kruskal算法中的并查集我们不能使用路径压缩，会破坏树的结构。比如两点间 a=>b，变成了a=> c <=b，那么答案就可能出错。可以按...

题目链接题意给你一个树，告诉你根节点。树上每个节点有一个权值 wiw_iwi​，你需要将树的每个节点进行染色。每次染色花费 111 的时间，一个点可以染色需要满足，根节点或者相邻节点已经被染色。染色的花费为 时间∗wi时间*w_i时间∗wi​，求全部染色的最小花费。思路首先权值最大点和其父节点染色操作是连续的。假设 x,y,zx,y,zx,y,z 三点，xxx 和 yyy 染色连续...

题目连接题意给你两个长度分别为 n，m的正整数序列 a，b。以矩阵形式给出所有 ai{a_i}ai​ 和 bjb_jbj​（1≤i≤n,1≤j≤m） 的大小关系（&amp;gt;,&amp;lt;,=）。构造符合条件的 a 和 b序列，且 a，b 中最大元素尽量小。无解，输出No。思路将每个元素设为一个节点，两者元素如果相同则用并查集合并，最后对合并后的点建图。如a&amp;gt;b，b到a存在一条单向边a&amp;...

DescriptionN children are playing Rochambeau (scissors-rock-cloth) game with you. One of them is the judge. The rest children are divided into three groups (it is possible that some group is emp

In order to strengthen the defense ability, many stars in galaxy allied together and built many bidirectional tunnels to exchange messages. However, when the Galaxy War began, some tunnels were dest

DescriptionFarmer John's pastoral neighborhood has N farms (2 <= N <= 40,000), usually numbered/labeled 1..N. A series of M (1 <= M < 40,000) vertical and horizontal roads each of varying lengths

题目大意：给一个较长的01串，每行给你一条信息，在某一范围内1的个数是奇数还是偶数个，问前几条的信息是不矛盾的。这题和 HDU3038 有些相似，可以先写了HDU3038。思路：这题数据范围较大需要离散化，说白就是给某个数起一个别名，因为最多就5000组范围，所以开10000多一点就行了  (为什么我开5000大小a了。。。1.首先设0为偶，1为奇，两个范围内  1数量的奇偶性

Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述： 第一种说法是"1 X Y"，表示X和Y是同类。 第二种说法是"2 X Y"，表示X吃Y。 此人对N个动物

DescriptionAfter having drifted about in a small boat for a couple of days, Akira Crusoe Maeda was finally cast ashore on a foggy island. Though he was exhausted and despaired, he was still fortun

Problem DescriptionBackground Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with b

C. Rumortime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputVova promised himself that he would never play com

Problem DescriptionTT and FF are ... friends. Uh... very very good friends -________-bFF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game.

水一发，这才是一个入门题应有的样子 (ಥ_ಥ)  ，前一道看了半天，还是我太菜了ORZ，现在大概明白并查集是个啥回事了，代码和模板还是差不多，不过少了点东西，如有错误欢迎指正。题目：Problem DescriptionToday is Ignatius' birthday. He invites a lot of friends. Now it's dinner time

Wireless NetworkTime Limit: 10000MS Memory Limit: 65536KTotal Submissions: 32072 Accepted: 13371DescriptionAn earthquake takes place in Southeast Asia. The ACM