#P18670. Shuttle Tour

    ID: 18006 传统题 4000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-树链剖分有限候选集缩减普通线段树二分查找DFS 序排序LCA欧拉序ST 表贡献法

Shuttle Tour

Shuttle Tour

Prof.Chen 在 ICPC 区域赛中夺冠,取得了下一年 ICPC 世界总决赛的参赛资格。为了在即将到来的总决赛中取得好成绩,他和队友正在 Byteburg 参加 ICPC 决赛前训练营。

Byteburg 是一座美丽的城市,有 nn 处景点,编号为 1,2,…,n1,2,\ldots,n。景点之间有 n−1n-1 条双向道路,任意两个地点都可以直接或间接到达。城中至多有 5050 个地点恰好与一条道路相连。

遗憾的是,有些景点可能没有开放;也可能全部开放。每天完成五个小时的训练后,Prof.Chen 都会浏览旅游网站查看开放情况,并制定穿梭游览计划。你需要处理 qq 个操作,操作有以下两种:

  • 1 x:切换编号为 xx 的景点的开放状态。如果原来开放,就将其关闭;如果原来关闭,就将其开放。
  • 2 l r:Prof.Chen 计划乘车游览编号在 [l,r][l,r] 内的每个开放景点。车辆可以从任意一个地点出发,沿道路行驶,最终返回出发地点,并使所有这些开放景点都至少被访问一次。**即使某个地点的景点关闭,车辆仍然可以到达或经过该地点。**出发地点和路线都由 Prof.Chen 自由选择,他希望路线的总长度最小。

请对每个第二类操作求出最短路线的长度。注意,[l,r][l,r] 是原始景点编号的区间,途中也可以经过该区间之外的地点。

输入格式

第一行包含两个整数 n,qn,q,满足 1≤n,q≤2000001\le n,q\le200000,分别表示地点数量和操作数量。

第二行包含一个长度为 nn 的字符串 SS,每个字符为 0 或 1。Si=0S_i=0 表示编号为 ii 的景点初始关闭,Si=1S_i=1 表示初始开放。

接下来的 n−1n-1 行,每行包含三个整数 ui,vi,wiu_i,v_i,w_i,满足 1≤ui,vi≤n1\le u_i,v_i\le n、ui≠viu_i\ne v_i、1≤wi≤1091\le w_i\le10^9,表示一条连接 uiu_i 和 viv_i、长度为 wiw_i 的双向道路。保证所有地点互相连通。

接下来的 qq 行,每行按上述格式描述一个操作:

  • 1 x 中,1≤x≤n1\le x\le n。
  • 2 l r 中,1≤l≤r≤n1\le l\le r\le n。

保证恰好与一条道路相连的地点不超过 5050 个。

输出格式

对于每个第二类操作,输出一行整数,表示所需路线的最小总长度。

如果 [l,r][l,r] 内的景点全部关闭,输出 -1。如果其中只有一个景点开放,可以直接从该地点出发并停留,路线长度为 00。

样例输入 1

5 6
10110
1 2 1
1 3 10
2 4 100
3 5 1000
2 1 5
1 3
2 1 5
2 2 4
2 5 5
2 1 1

样例输出 1

222
202
0
-1
0