#P2322. [BeiJing2011]梦想封印

    ID: 1355 传统题 1000ms 128MiB 尝试: 612 已通过: 156 难度: 9 上传者: 标签>CF2600省选/NOI-逆序处理删除线性基异或消元等价类划分有序集合广度优先搜索

[BeiJing2011]梦想封印

题目描述

渐渐地,Magic Land 上的人们对那座岛屿上的各种现象有了深入的了解。

为了分析一种奇特的称为梦想封印(Fantasy Seal)的特技,需要引入如下的概念:

每一位魔法的使用者都有一个「魔法脉络」,它决定了可以使用的魔法的种类。

一般地,一个「魔法脉络」可以看作一个无向图,有 nn 个结点及 mm 条边,将结点编号为 1∼n1 \sim n,其中有一个结点是特殊的,称为核心(Kernel),记作 11 号结点。每一条边有一个固有(即生成之后再也不会发生变化的)权值, 是一个不超过 uu 的自然数。

每一次魔法驱动,可看作是由核心(Kernel)出发的一条有限长的道路(Walk),可以经过一条边多次,所驱动的魔法类型由以下方式给出:

将经过的每一条边的权值异或(xor)起来,得到 ss。

如果 ss 是 00,则驱动失败,否则将驱动编号为 ss 的魔法(每一个正整数编号对应了唯一一个魔法)。

需要注意的是,如果经过了一条边多次,则每一次都要计入 ss 中。

这样,魔法脉络决定了可使用魔法的类型,当然,由于魔法与其编号之间的关系尚未得到很好的认知,此时人们仅仅关注可使用魔法的种类数。

梦想封印可以看作是对「魔法脉络」的破坏:

该特技作用的结果是,「魔法脉络」中的一些边逐次地消失。

我们记总共消失了 qq 条边,按顺序依次为 dis1,dis2,…,disqdis_1, dis_2, \ldots , dis_q。

给定了以上信息,你要计算的是梦想封印作用过程中的效果,这可以用 q+1q+1 个自然数来描述:

ans0ans_0 为初始时可以使用魔法的数量。

ans1ans_1 为 dis1dis_1 被破坏(即边被删去)后可以使用魔法的数量。

ans2ans_2 为 dis1dis_1 及 dis2dis_2 均被破坏后可使用魔法的数量。

⋯\cdots

ansqans_q 为 dis1,dis2,…,disqdis_1, dis_2, \ldots , dis_q 全部被破坏后可以使用魔法的数量。

输入格式

第一行包含三个正整数 n,m,qn,m,q。

接下来的 mm 行,每行包含 33 个整数,aia_i, bib_i, wiw_i,表示一条权为 wiw_i 的与结点 aia_i, bib_i 关联的无向边,其中 wiw_i 是不超过 uu 的自然数。

接下来 qq 行,每行一个整数:disidis_i。

输出格式

一共包 q+1q+1 行,依次为 ans0,ans1,…,ansqans_0, ans_1, \ldots , ans_q。

3 3 2
1 2 1
2 3 2
3 1 4
1
3
5
2
0

样例说明 1

初始时可使用编号为 1,3,4,6,71, 3, 4, 6, 7 的魔法。

在删去第 11 条边(连结 1,21,2 结点的边)后,可使用 44 和 66 号魔法。

第 33 条边(连结第 1,31,3 结点的边)也被删去后,核心(Kernel)即结点 11 孤立,易知此时无法使用魔法。

5 7 7
1 2 1
1 3 1
2 4 2
2 5 2
4 5 4
5 3 9
4 3 1
7
6
5
4
3
2
1
15
11
5
2
2
1
1
0

数据规模和约定

所有数据保证该无向图不含重边、自环。

所有数据保证不会有一条边被删除多次,即对于不同 ii 和 jj,有 disi≠disjdis_i\neq disj。

对于 30%30\% 的数据中 n,m,q≤50n,m,q \leq 50,u≤100u \leq 100;

对于 60%60\% 的数据中 n,m≤300n,m \leq 300,q≤50q \leq 50,u≤109u \leq 10^9;

对于 80%80\% 的数据,n≤300n \leq 300,m,q≤5000m,q \leq 5000,u≤1018u \leq 10^18;

对于 100%100\% 的数据,n≤5000n \leq 5000,m,q≤20000m,q \leq 20000,u≤1018u \leq 10^18、

题目来源

Day3