编程介的小学生 2019-04-28 21:20 采纳率: 20.5%
浏览 201

数据结构里的树的合并转移的算法,利用C语言的程序的设计的实现的方式怎么做?

Problem Description
There is a tree, n nodes, numbered from 1 to n, each node has a weight, but each leaf node is the father of the root,

we call such a tree as Transmigration tree, The root of each tree is node 1.

We need to minimize the sum of weights that node u to node v and know who is the biggest weights node in this path.

Input
The first line of the input is a single integer T(T≤10), indicating the number of testcases.

Then T testcases follow.In each testcase,

The first line contains two integers n,q, the number of nodes and inquiry(2≤n≤50000,1≤q<100000).

The second line contains n−1 integers Ai(1≤Ai≤i) represent the node i+1's father is node Ai.

The third line contains n integers Bi(1≤i≤n,0≤Bi≤1000) represent the node i's weight is Bi.

Then q line follow,each line contains two integers u,v,it represents a query(1≤u,v≤n).

Output
For each query,we should output one line "x y", where x is the smallest the sum of weights that node u to node v and y is the weight of the biggest weights node in this path.(If there are multiple paths, please calculating the maximum node weights largest)

Sample Input
1
5 1
1 2 3 4
413 127 263 869 960
1 5

Sample Output
1373 960

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
    • ¥15 vs2019中数据导出问题
    • ¥20 云服务Linux系统TCP-MSS值修改?
    • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
    • ¥20 怎么在stm32门禁成品上增加查询记录功能
    • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
    • ¥50 NT4.0系统 STOP:0X0000007B
    • ¥15 想问一下stata17中这段代码哪里有问题呀
    • ¥15 flink cdc无法实时同步mysql数据
    • ¥100 有人会搭建GPT-J-6B框架吗?有偿