#P18710. Neighbourhood

    ID: 18046 传统题 10000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-点分树点分治容斥去重子树转区间根号分块整块懒标记块内排序二分查找双指针合并有序序列

Neighbourhood

Neighbourhood

给定一棵有 nn 个顶点的树,每条边都有一个正整数权值 wiw_i。树上两点之间的距离是它们之间唯一路径的边权之和。

需要处理 qq 次以下两种操作:

  • 1 i c:把第 ii 条边的权值 wiw_i 改为 cc。
  • 2 x d:统计满足从 xx 到 yy 的距离不大于 dd 的顶点 yy 的数量,其中 1≤y≤n1\le y\le n。

输入格式

第一行包含两个整数 n,qn,q(2≤n≤2×1052\le n\le2\times10^5,1≤q≤2×1051\le q\le2\times10^5)。

接下来的 n−1n-1 行,每行包含三个整数 xi,yi,wix_i,y_i,w_i(1≤xi,yi≤n1\le x_i,y_i\le n,1≤wi≤1091\le w_i\le10^9),表示树中的一条边。边按照输入顺序从 11 到 n−1n-1 编号。

接下来的 qq 行,每行描述一次操作:

  • 1 i c(1≤i≤n−11\le i\le n-1,1≤c≤1091\le c\le10^9)。
  • 2 x d(1≤x≤n1\le x\le n,0≤d≤2×10140\le d\le2\times10^{14})。

输入只有一组数据,不包含测试组数。原题没有保证至少有一次第二类操作。

输出格式

对于每次第二类操作,输出一行,包含一个整数,表示满足条件的顶点数量。

样例

样例输入

3 7
1 2 3
2 3 1
2 2 1
2 1 3
2 3 4
1 1 1
2 2 1
2 1 0
2 3 1

样例输出

2
2
3
3
1
2