#P9092. 「HNOI2021 省集 Day7」色

    ID: 5176 传统题 3000ms 512MiB 尝试: 4 已通过: 2 难度: 7 上传者: 标签>难度分类提高+/省选-图论Kruskal数据结构普通并查集有序多重集合模拟与实现技巧增量维护CF2300

「HNOI2021 省集 Day7」色

题目描述

给定一个 nn 个点,mm 条边的无向连通图,图有边权,每个点有一个颜色,颜色总数为 cc。

有 qq 次操作,每次操作改变某一个点的颜色,每次操作后求图中不同颜色点的最短距离。

输入格式

从标准输入读入。

第一行为四个正整数 n,m,c,qn,m,c,q。

接下来 mm 行,每行三个整数 u,v,wu,v,w,表示一条连接顶点 uu 和 vv、权值为 ww 的无向边。

接下来一行 nn 个正整数表示每个点的初始颜色。

接下来 qq 行每行两个正整数 x,yx,y ,表示将 xx 点的颜色修改为 yy。

输出格式

输出到标准输出。

对于 qq 次操作,每次操作输出图中不同颜色点的最短距离。

样例

样例 1

3 2 3 4
1 2 3
2 3 1
1 1 2
3 3
2 3
1 2
2 2
1
3
3
1

样例 2

见附加文件中 color2.in 与 color2.out。

数据范围

  • 对于 20%20\% 的数据,n,m,q≤3×103n,m,q\le 3\times 10^3。
  • 对于 50%50\% 的数据,n,q≤5×104n,q\le 5\times 10^4。
  • 对于 100%100\% 的数据,1≤n≤2×1051\le n\le 2\times 10^5,$n-1\le m\le \min(\frac{n\times (n-1)}{2},3\times 10^5)$,颜色数 c≤nc\le n,1≤q≤2×1051\le q\le 2\times 10^5,0≤w≤1060\le w\le 10^6,保证任意时刻图中颜色至少存在两种。