小Y的问题

小Y的问题

【问题描述】
有个孩子叫小 Y，一天，小 Y 拿到了一个包含 n 个点和 n-1 条边的无向连通图，图中的
点用 1~n 的整数编号。小 Y 突发奇想，想要数出图中有多少个“Y 字形”。
一个“Y 字形”由 5 个不同的顶点 A、B、C、D、E 以及它们之间的 4 条边组成，其中 AB、
BC、BD、DE 之间有边相连，如下图所示。

同时，无向图中的每条边都是有一定长度的。一个“Y 字形”的长度定义为构成它的四条
边的长度和。小 Y 也想知道，图中长度最大的“Y 字形”长度是多少。

【输入】
第一行包含一个整数 n，表示无向图的点数。
接下来 n 行，每行有 3 个整数 x、y、z，表示编号为 x 和 y 的点之间有一条长度为 z 的
边。

【输出】
输出包含 2 行。
第 1 行包含一个整数，表示图中的“Y 字形”的数量。
第 2 行包含一个整数，表示图中长度最大的“Y 字形”的长度。

【输入输出样例 1】
question.in
7
1 3 2
2 3 1
3 5 1
5 4 2
4 6 3
5 7 3
question.out
5
9
【输入输出样例 1 说明】
图中共有 5 个“Y 字形”，如图中用红色标出的部分所示。
其中，长度最大的“Y 字形”是编号 3、5、7、4、6 的顶点构成的那一个，长度为 9。

【数据规模与约定】
对于 30%的数据，n≤10
对于 60%的数据，n≤2,000
对于 100%的数据，n≤200,000，1≤x,y≤n，1≤z≤10,000

解析

这个题有没有很恶心，太恶心了，看到这个题，完全没思路，但是看到了讲解，一下就懂了，很木有很烦！！！
不说废话 要想做到正解，看到数据范围就知道会超时，要做到时间复杂度为O（N）才能拿到正解！！！
30分
简单说一下30分的做法

因为数据范围只有n≤10，所以可以枚举4条边，看看是否有三条边中有一个公共点x,再从这三条边中寻找是否有一个点y，y点还连着一条边，如果符合，计数加1，在把边权相加，与最大值比较。

60分
数据范围为n≤2,000，限时1秒的话，能承受O（N^2）的算法
首先要做预处理，读图时要记录每个点的度（有多少出边）
再画个图

这样时间复杂度就降到了O（N^2）

100分
数据范围 n≤200,000，O（N^2）也会超时，需要把时间复杂度降到O(N)
首先还是要预处理，不仅要记录每个点的度，还要记录每个点的出边的最大值，次大值，第三大值，为什么要记录三个呢，一会看图就知道了
找Y形的时候与60分一样

好了这题就完了！！！！！！