Day 1:

     第一次参加noip。小激动，小紧张，这些正常的情绪就不用说了。唯一值得一提的是 我早上步行去郑大工学院的时候迷路了，直接转进了隔壁的河南农大，绕了半天找不到机房，还给几个同学打了电话可就是没人接……于是就在保安异样的目光下灰溜溜地走出了校门= =...然后还算好，总算提前半个小时来到了考点。。。

    然后找座位的时候我遇到了奇怪的事情！！我的座位旁边是夏五岳……同校+同语言……天知道负责人的随机数生成器是出了什么问题= =不过看起来我们似乎没有被监考的志愿者盯上？那就这样吧= =于是，按照平时的习惯，我先敲好了头文件和快速读入……（别问我为什么还有快速读入……我只是懒得每次打scanf又怕cin被卡……）然后……看题……

A: 生活大爆炸版石头剪刀布

 给出五种手势的胜负关系，A、B的出拳循环节和总共进行的轮数N，求游戏结束时两人各自的输赢次数。

N <= 200。N <= 200。N <= 200。N <= 200。

 QAQ……请告诉我我没有看错数据范围。请告诉我200遍我没有看错数据范围。不对……我是不是走错考场考成普及组了？可是普及组不应该是下午比赛吗……好吧好吧，我再检查200遍题目就开始敲代码。。。

     于是开考后三十分钟，我开始了无脑模拟。话说这题要是数据范围再大那么几个零是不是就可以变成数论题了？= = 看来出题人有着特别的送分技巧……就这么敲完了模拟。果断开下一题？算了还是再检查200遍题目吧……万一理解错了呢……

    然后开始了第二题：

B:联合权值

 $无向联通图G有n个节点，n-1条边。点从1~n依次编号，编号为i的点权值为W_i，每条边长度均为1.$

$图上两点u,v的距离定义为u,v的最短距离。$

$对于图上的点对(u,v)，若它们的距离为2，则它们之间会产生W_u \times W_v的联合权值。$

 $ 请问图上可能产生联合权值的有序点对中，联合权值最大的是多少？所有权值之和是多少？$

$n \leq 200000$

     好吧我终于敢确定自己没有报成普及组了……

    首先看到无向连通图和n-1条边，可知这是一棵树……（可是您把这两条信息都放在开头和直接说这是一棵树的区别在哪里QAQ）

    然后很容易就会想到用树分治的方法统计。于是dfs一下，讨论一下兄弟节点和祖孙节点就可……等等。。。没有那么麻烦！我可以直接枚举中点！

    因为要求的是树上距离为2的点对，根据树上路径的存在性&唯一性，可知它们有且只有一个公共的邻接点。于是我们可以直接把这个中点拎出来，这时很容易看出它的所有邻接点之间都可以产生“联合权值”。那么我们求的所有权值之和就是$\sum\limits_{i=1}^N(\sum\limits_{u,v \in adj_i, u \neq v} W_u \times W_v)$.

    但是每个节点的所有邻接点“两两之间的乘积之和”怎么求呢……对于任意一个中点i，我们可以把表达式写成这样：$$S_i = \sum_{j \in adj_i} (W_j \times (\sum_{k \in adj_i} W_k) - W_j)$$ 然后合并同类项，就成了$$S_i ={ (\sum_{j \in adj_i} W_j)} ^ 2 - \sum_{j \in adj_i} W_j^2$$。这样对于每个中点i的处理就只需$O(|adj_i|)$的时间，而每条边只处在两个节点的邻接表中，因此总时间复杂度为O(n)。

   然后……为什么数据是个$O(nlogn)$级别的规模呢……表示不解。。。难道我证错了？

再然后……第三题改天再和day2一起写吧 ……反正我只写了70分算法= =

NOIP2014·水渣记 & 解题报告