New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

1880: 树上路径

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计

题目描述

给出一棵有 n 个节点的树，有 m 个如下所示的操作：
将两个节点之间的路径上的边的权值均加一。
查询两个节点之间的那一条边的权值，保证两个节点直接相连。
初始边权均为 0。

输入格式

第一行两个整数 n,m，含义如上。1≤n≤100000，1≤m≤100000。
接下来 n−1 行，每行两个整数 u,v，表示 u,v 之间有一条边。
接下来 m 行，每行格式为 op u v，op=P 代表第一个操作，op=Q 代表第二个操作。

输出格式

若干行。对于每个查询操作，输出一行整数，代表查询的答案。

输入样例 复制 

4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4

输出样例 复制 

2
1
2

数据范围与提示

来源：USACO 2011.12