编程介的小学生 2019-03-30 19:48 采纳率: 20.5%
浏览 195

计算有多少条路经可以到达,采用C程序的语言算法的实现怎么做

Problem Description
bobo has a tree, whose vertices are conveniently labeled by 1,2,…,n.

Let f(a,b) be the minimum of vertices not on the path between vertices a and b.

There are q queries (ui,vi) for the value of f(ui,vi). Help bobo answer them.

Input
The input consists of several tests. For each tests:

The first line contains 2 integers n,q (4≤n≤106,1≤q≤106). Each of the following (n - 1) lines contain 2 integers ai,bi denoting an edge between vertices ai and bi (1≤ai,bi≤n). Each of the following q lines contains 2 integer u′i,v′i (1≤ui,vi≤n).

The queries are encrypted in the following manner.

u1=u′1,v1=v′1.
For i≥2, ui=u′i⊕f(ui - 1,vi - 1),vi=v′i⊕f(ui-1,vi-1).

Note ⊕ denotes bitwise exclusive-or.

It is guaranteed that f(a,b) is defined for all a,b.

The task contains huge inputs. scanf in g++ is considered too slow to get accepted. You may (1) submit the solution in c++; or (2) use hand-written input utilities.

Output
For each tests:

For each queries, a single number denotes the value.

Sample Input
4 1
1 2
1 3
1 4
2 3
5 2
1 2
1 3
2 4
2 5
1 2
7 6

Sample Output
4
3
1

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题