7-2 二叉树加权距离 (100 分)
二叉树结点间的一种加权距离定义为：上行方向的变数×3 +下行方向的边数×2 。上行方向是指由结点向根的方向，下行方向是指与由根向叶结点方向。 给定一棵二叉树T及两个结点u和v，试求u到v的加权距离。
输入格式:
第1行，1个整数N，表示二叉树的结点数，(1≤N≤100000)。
随后若干行，每行两个整数a和b，用空格分隔，表示结点a到结点b有一条边，a、b是结点的编号，1≤a、b≤N；根结点编号为1，边从根向叶结点方向。
最后1行，两个整数u和v，用空格分隔，表示所查询的两个结点的编号，1≤u、v≤N。
输出格式:
1行,1个整数，表示查询的加权距离。
存好节点深度，再一步一步找父亲，父亲相同即停止。
类似于并查集做法，但是不是找到根节点，而是找到最小公共祖先。
#include <iostream>
//int lef[100010];
//int rit[100010];
int fa[100010];
int dep[100010];
using namespace std;
int main()
{
int m;
int a, b;
cin >> m;
for (int i = 1; i < m; i++) {
cin >> a >> b;
fa[b] = a;
// if (!lef[a]) lef[a] = b;
//else rit[a] = b;
dep[b] = dep[a] + 1;
}
cin >> a >> b;
int sum = 0;
while (a != b) {
if (dep[a] >= dep[b]) {
sum += 3;
a = fa[a];
}
else {
sum += 2;
b = fa[b];
}
}
cout << sum;
}
7-3 修轻轨 (100 分)
长春市有n个交通枢纽，计划在1号枢纽到n号枢纽之间修建一条轻轨。轻轨由多段隧道组成，候选隧道有m段。每段候选隧道只能由一个公司施工，施工天数对各家公司一致。有n家施工公司，每家公司同时最多只能修建一条候选隧道。所有公司可以同时开始施工。请评估：修建这条轻轨最少要多少天。。
输入格式:
第1行，两个整数n和m，用空格分隔，分别表示交通枢纽的数量和候选隧道的数量，1 ≤ n ≤ 100000，1 ≤ m ≤ 200000。
第2行到第m+1行，每行三个整数a、b、c，用空格分隔，表示枢纽a和枢纽b之间可以修建一条双向隧道，施工时间为c天，1 ≤ a, b ≤ n，1 ≤ c ≤ 1000000。
输出格式:
输出一行，包含一个整数，表示最少施工天数。
克鲁斯卡尔法，n和1连通就停止了。
// 6.9.3.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include<algorithm>
#define maxn 100010
int father[maxn]; // 储存i的father父节点
int ans = 0;
int n, m;
struct eg {
int a, b, c;
bool operator <(struct eg& ttt)const {
return c < ttt.c;
}
}edge[200010];
void makeSet() {
for (int i = 0; i < maxn; i++)
father[i] = i;
}
int Find(int x) { // 迭代找根节点
int root = x; // 根节点
while (root != father[root]) { // 寻找根节点
root = father[root];
}
while (x != root) {
int tmp = father[x];
father[x] = root; // 根节点赋值
x = tmp;
}
return root;
}
void Union(int x, int y) { // 将x所在的集合和y所在的集合整合起来形成一个
int a, b;
a = Find(x);
b = Find(y);
father[a] = b; // y连在x的根节点上 或father[b] = a为x连在y的根节点
}
void Kruskal() {
ans = 0;
int summ = 0;
for (int i = 1; i <= m; i++) {
if (Find(edge[i].a) != Find(edge[i].b)) {
Union(edge[i].a, edge[i].b);
ans = edge[i].c;
summ++;
/* if (summ == n - 1) {
ans= edge[i].c;
return;
}*/
if (Find(1) == Find(n)) {
return;
}
}
}
}
using namespace std;
int main()
{
cin >>n >> m;
int w, e, r;
for (int i = 1; i <= m; i++) {
cin >> w >> e >> r;
edge[i] = { w,e,r };
}
for (int i = 1; i <= n; i++) {
father[i] = i;
}
sort(&edge[1], &edge[m + 1]);
Kruskal();
cout << ans;
}
// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单
// 入门使用技巧:
// 1. 使用解决方案资源管理器窗口添加/管理文件
// 2. 使用团队资源管理器窗口连接到源代码管理
// 3. 使用输出窗口查看生成输出和其他消息
// 4. 使用错误列表窗口查看错误
// 5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
// 6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
小唐正在学习数据结构。他尝试应用数据结构理论处理数据。最近，他接到一个任务，要求维护一个动态数据表，并支持如下操作：
插入操作（I）：从表的一端插入一个整数。
删除操作（D）：从表的另一端删除一个整数。
取反操作（R）：把当前表中的所有整数都变成相反数。
取最大值操作（M）：取当前表中的最大值。
如何高效实现这个动态数据结构呢？
输入格式:
第1行，包含1个整数M，代表操作的个数， 2≤M≤1000000。
第2到M+1行，每行包含1个操作。每个操作以一个字符开头，可以是I、D、R、M。如果是I操作，格式如下：I x, x代表插入的整数，-10000000≤x≤10000000。 。
输出格式:
若干行，每行1个整数，对应M操作的返回值。如果M和D操作时队列为空，忽略对应操作。
聪明的做法是保存翻转的flag，flag不同相应取最大值/最小值的相反数，输入数时也考虑输入的正负，最值暴力写就好了，还可以优化的地方就是保存上次去最值的区间，以及最值取到的位置来简化运算，不过这种优化会被特殊数据卡死，单调队列就挺好了，还利于维护，不过要自己写或者使用deque（我只知道有），因为要同时头取最值，尾部删值。
我偷懒了hhhhh。
#include <iostream>
#include<stdio.h>
#include<queue>
#pragma warning(disable : 4996)
int kk[1000010];
int max;
std::queue<int> dddd;
using namespace std;
int main()
{
int maxi1=0,maxi2=0,m;
int max;
int top = 0;
int end = 1;
int hao = 0;
char d;
int flag = 0;
scanf(" %d",&m);
for (int i = 1; i <= m; i++) {
scanf(" %c",&d);
switch (d) {
case 'I':
int j;
scanf(" %d",&j);
if (!flag)kk[++top] = j;
else kk[++top] = -j;
break;
case 'D':
if(end<=top)
end++;
break;
case 'R':
flag^=1;
break;
case 'M':
if (end <= top) {
int b = end;
if (!flag) {
max = kk[end];
if (maxi1 < end)
while (b <= top) {
if (max <= kk[b]) {
max = kk[b];
maxi1 = b;
}
b++;
}
else {
b = maxi1;
while (b <= top) {
if (max <= kk[b]) {
max = kk[b];
maxi1 = b;
}
b++;
}
}
dddd.push(max);
break;
}
else {
max = kk[end];
if (maxi2 < end)
while (b <= top) {
if (max > kk[b]) {
max = kk[b];
maxi2 = b;
}
b++;
}
else {
b = maxi2;
while (b <= top) {
if (max > kk[b]) {
max = kk[b];
maxi2 = b;
}
b++;
}
}
dddd.push(-max);
break;
}
}
}
}
while (!dddd.empty()) {
printf("%d\n", dddd.front());
dddd.pop();
}
}