#1915. 黑白无常

黑白无常

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定N\red{N }个点 M\red{M}条边的带权无向图,每个点有颜色:黑或者白。

Q\red{Q }个操作,每个操作是下面其中一种:

1 X\red{1 ~X :}表示把 x\red{x }节点的颜色取反(黑变成白,白变成黑);

2 A B\red{2 ~A~ B :}查询两端的颜色分别是 A\red{A }B\red{B}A/B\red{A/B }取值为0/1\red{0/1,}代表 黑/白)的边的权值之和。

输入格式

第一行一个数T\red{T ,}表示T\red{T }组数据。

每组数据第一行两个数N\red{N }M\red{M}

接下来一行有N\red{N }个数,Ai=0\red{A_i=0 }表示第i\red{i }个点初始是黑色,否则是白色。

接下来 M\red{M}行,每行三个数,表示 ui\red{u_i}vi\red{v_i}有一条边,权值为 wi\red{w_i}

接下来一行是Q\red{Q }

接下来 Q\red{Q}行,分别是 "1 X\red{1~ X}" 或者 "2 A B\red{2~ A ~B}" 的形式。

输出格式

对于每个"询问 2\red{2}",输出一行,表示两端点恰好和指定的"A/B\red{A/B}"一致的边的权值和。

样例

输入样例

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

输出样例

6
3
3
3
0
4

提示

对于 10%\red{10\%}的数据,M=N1\red{M=N-1 ,}原图恰好是一棵树的形式;

对于另外 10%\red{10\%}的数据,N=30000\red{N=30000 ,}M=100000\red{M=100000 ,}图是完全随机构造的;

对于100%\red{100\% }的数据,T<=10,1<=N,M,Q<=100000\red{T<=10,1<=N,M,Q<=100000 }

小云雀c++高中组重现

未参加
状态
已结束
规则
ACM/ICPC
题目
4
开始于
2022-5-3 18:00
结束于
2022-5-5 18:00
持续时间
48 小时
主持人
参赛人数
27