问题 AN: 多彩的树
内存限制：512 MB
时间限制：8.000 S
评测方式：文本比较
命题人：
提交：48
解决：11
题目描述
给定一颗有n个节点的树
每条边都有一个颜色和长度
现给出q个查询
每个查询先将所有颜色值为c的边的长度改为d，
再查询节点u到节点v的最短距离
每次查询独立，互不影响。
即所有的长度变化只在这一次查询中生效
每条边都有一个颜色和长度
现给出q个查询
每个查询先将所有颜色值为c的边的长度改为d，
再查询节点u到节点v的最短距离
每次查询独立，互不影响。
即所有的长度变化只在这一次查询中生效
输入
n q
1 <= n , q <= 1e5
接下来n - 1行
每行 a b c d 表示a节点和b节点有一条长度为d并且颜色为c的边
1 <= a , b <= n
1 <= c <= n - 1
1 <= d <= 1e4
a1 , b1 , c1 , d1
......
an-1 , bn-1 , cn-1, dn-1
接下来q行
每行x , y , u , v
表示如果将所有颜色为x的边的长度修改为y
点u和v之间的距离是多少
x1 , y1 , u1 , v1
.........
xq , yq , uq , vq
1 <= x <= n - 1
1 <= y <= 1e4
1 <= u , v <= n
1 <= n , q <= 1e5
接下来n - 1行
每行 a b c d 表示a节点和b节点有一条长度为d并且颜色为c的边
1 <= a , b <= n
1 <= c <= n - 1
1 <= d <= 1e4
a1 , b1 , c1 , d1
......
an-1 , bn-1 , cn-1, dn-1
接下来q行
每行x , y , u , v
表示如果将所有颜色为x的边的长度修改为y
点u和v之间的距离是多少
x1 , y1 , u1 , v1
.........
xq , yq , uq , vq
1 <= x <= n - 1
1 <= y <= 1e4
1 <= u , v <= n
输出
对每个查询 输出一行答案
样例输入 复制
5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4
样例输出 复制
130
200
60