文道(laocooon@qq.com) 19:05:23
有一块很大的农场！农场里分成了 n 块农田,编号为 1-n，这些农田由 n-1 个沟渠联通 着。 这些沟渠中的一些已经干涸了，农场主想要让所有沟渠都保持有水。但是他只能在农田 里浇水。如果他在某块农田里浇了水，那么从这块农田到 1 号农田简单路径上的沟渠都会处 于有水的状态。显然，这样的路径只会有一条。 这个农场主想知道，他最少要浇几块农田，才能让所有沟渠都有水。
★数据输入
第一行输入一个整数 n。 接下来 n-1 行，每行三个整数 u，v，s(1<=u,v <=n)描述一条沟渠的状态，表示 u，v 之间有一条沟渠，s = 1 表示这条沟渠里有水，s = 2 表示这条沟渠干了。
★数据输出
第一行输出一个整数 k 表示最少的浇灌次数 20%：n < 10 40%: n < 100 100%:n < 100000
输入示例
5
1 2 2
2 3 2
3 4 2
4 5 2
输出示例
1
输入示例
5
1 2 1
2 3 2
2 4 1
4 5 1
输出示例
1
★实验任务
有一张无限大的图，图中的节点编号从1开始。图中节点由无向边连接，编号为i的节点分别与2i号节点和2i+1号节点连接，显然任意两个点之间的最短路是确定的且唯一的。最开始每条边上的花费都是0。 接下来有两种操作
给从u到v的最短路上的每条边都加上w的花费
计算走最短路从u到v的总花费（即路上所有边的花费和）
★数据输入
第一行输入一个整数q，表示操作的数量，接下来q行，每行第一个数字代表操作的类型，如果是1号操作，则紧接着输入u，v，w三个整数；如果是2号操作，接着输入u，v两个整数。
★数据输出
对于每一个2号操作，输出一行一个数字，代表路上的总花费
输入示例
7
1 3 4 30
1 4 1 2
1 3 6 8
2 4 3
1 6 1 40
2 3 7
2 2 4
输出示例
94
0
32
★数据范围
50% : q <= 10, 1≤u,v,w≤1000
100% : q <= 1000, 1≤u,v≤1000000,w <= 1e9
有一块很大的农场！农场里分成了 n 块农田,编号为 1-n，这些农田由 n-1 个沟渠联通 着。 这些沟渠中的一些已经干涸了，农场主想要让所有沟渠都保持有水。但是他只能在农田 里浇水。如果他在某块农田里浇了水，那么从这块农田到 1 号农田简单路径上的沟渠都会处 于有水的状态。显然，这样的路径只会有一条。 这个农场主想知道，他最少要浇几块农田，才能让所有沟渠都有水。
★数据输入
第一行输入一个整数 n。 接下来 n-1 行，每行三个整数 u，v，s(1<=u,v <=n)描述一条沟渠的状态，表示 u，v 之间有一条沟渠，s = 1 表示这条沟渠里有水，s = 2 表示这条沟渠干了。
★数据输出
第一行输出一个整数 k 表示最少的浇灌次数 20%：n < 10 40%: n < 100 100%:n < 100000
输入示例
5
1 2 2
2 3 2
3 4 2
4 5 2
输出示例
1
输入示例
5
1 2 1
2 3 2
2 4 1
4 5 1
输出示例
1
★实验任务
有一张无限大的图，图中的节点编号从1开始。图中节点由无向边连接，编号为i的节点分别与2i号节点和2i+1号节点连接，显然任意两个点之间的最短路是确定的且唯一的。最开始每条边上的花费都是0。 接下来有两种操作
给从u到v的最短路上的每条边都加上w的花费
计算走最短路从u到v的总花费（即路上所有边的花费和）
★数据输入
第一行输入一个整数q，表示操作的数量，接下来q行，每行第一个数字代表操作的类型，如果是1号操作，则紧接着输入u，v，w三个整数；如果是2号操作，接着输入u，v两个整数。
★数据输出
对于每一个2号操作，输出一行一个数字，代表路上的总花费
输入示例
7
1 3 4 30
1 4 1 2
1 3 6 8
2 4 3
1 6 1 40
2 3 7
2 2 4
输出示例
94
0
32
★数据范围
50% : q <= 10, 1≤u,v,w≤1000
100% : q <= 1000, 1≤u,v≤1000000,w <= 1e9
