TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P6832
  • 問題
  • P6832异或最短路
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 2s,512m
    問題説明

    何老板给你一个有$n$个点$m$条边的连通的无向图,节点编号$1$到$n$,每条边都有一定的权值。
    图中一条路径的长度是指:该路径经过的边的边权全部异或起来的结果。(如果路径上某条边被经过了$k$次,那么在进行异或运算时,该边边权也应该被异或$k$次)

    接下来有三种操作:
    $1 \ x \ y \ d$,将图中点$x$与点$y$间连一条权值为$d$的边。保证在此操作之前,$x,y$两点间没有边相连;
    $2 \ x \ y $,将图中点$x$与点$y$间的边删除。保证在此操作前,$x,y$两点之间有边相连,且操作后图仍然连通;
    $3 \ x \ y$,计算从点$x$到点$y$的最短路径长度(注意,该路径可能不是简单路径)。

    对于每个$3$号操作,你都需要快速计算出结果。

    入力形式

    第一行,两个整数$n,m$
    接下来$m$行,每行三个整数$x \ y \ d $表示一条边的两个端点和边权
    接下来一个整数$q$,表示操作的总次数
    接下来$q$行,每行表示一次操作。

    出力形式

    若干行,每行一个整数,对应一次$3$号操作的计算结果。

    サンプル入力

    5 5
    1 2 3
    2 3 4
    3 4 5
    4 5 6
    1 5 1
    5
    3 1 5
    1 1 3 1
    3 1 5
    2 1 5
    3 1 5

    サンプル出力

    1
    1
    2

    ヒント

    \(n,m,q<=200000\)
    $0<=d<=2^{30}-1$
    $1\leq x\lt y\leq n$

    本题数据由nodgd构造


    ソース  CF938G