TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1508
  • 题目
  • P1508树上距离统计 | 内含题解
    限制 : 时间限制 : 20000 MS   空间限制 : 262144 KB
    评测说明 : 2s,256MB
    问题描述

    一棵无根树,两个节点的距离定义为它们路径上有多少条边。对每个节点,计算所有节点到它的距离的平方和。

    点击查看此题原内容“NK月赛题解”

    A.模拟+离散化
    按小镇的位置由小到大排序(离散化),然后从左到到右扫一遍(模拟),对于位置为X的村庄,加油站最远能建在X+K的位置,也就意味着这个加油站服务的区域是从X到X+K+K。



    B.模拟+离散化
    1.先按点的x坐标由小到大排序(离散化)
    2.从左到到右扫一遍(模拟),依次计算相邻两个点的斜率,记录下最大者即可。
    注意:
    只需计算相邻两个点的斜率
    为避免误差 double=double()/double()
    <cmath>包中的函数fabs()用于求实数的绝对值




    C.“KMP”或者“最小表示法”都可解决
    比如对于两个字符串A"34567"和B"73456",要判断B是否跟A一样可采用下列方式
    1.A=A+A="3456734567" (处理环形)
    2.用KMP判断B是否是A的子串,若是,表明B和A实际是一样的。




    D.图论,拓扑排序
    首先构图,若存在条件“a的钱比b多”则从b引一条有向指向a;
    然后拓扑排序,若无法完成排序则表示问题无解(存在圈);
    若可以得到完整的拓扑序列,则按序列顺序进行递推:
    设f[i]表示第i个人能拿的最少工资数;
    首先所有f[i]=100(题目中给定的最小值);
    然后考察拓扑序列中的每个点i,若在它之前的点j存在有向边(j,i),则表示f[i]必须比f[j]大,因此我们令f[i] = Max { f[i],f[j]+1 }即可;
    递推完成之后所有f[i]的值也就确定了,而答案就等于f[1]+…+f[n]。
    注意:可能出现m条意见并没有把所有保镖讨论完的情况,也就是某些保镖没有出现在m个人的意见中,那么这些人的工资直接就是100元




    E.动态规划
    f[i][j]从第i个括号开始的连续j个括号最少需添加的括号数
    f[i][j]的值应该是下列两种情况的最小者
    1:min{f[i][k-1]+f[k+i][i+j-k-2]}(i后第j个括号和i后第k个括号匹配) 1=<k<=j-1
    2:f[i][j-1]+1

    输入格式

    第一行一个整数 \(n\) ,即树的节点数量,节点编号为 $1,2,\dots,n$ 。

    接下来 \(n-1\) 行,每行两个整数 \(x,y\) ,表示树的一条边。

    输出格式

    输出 \(n\) 行,第 \(i\) 行输出一个整数,为节点 \(i\) 的答案。

    样例输入

    6
    1 2
    1 3
    3 4
    3 5
    2 6

    样例输出

    14
    24
    16
    34
    34
    46

    提示

    对于30%的数据, \(n\leq 10^3\)
    对于50%的数据, \(n\leq 10^4\)
    对于70%的数据, \(n\leq 10^5\)
    对于100%的数据, $2\leq n\leq 10^6$ 。