Skip to content

1121: 啊好问题

题目

题目描述

Icefox有一棵 $n$ 个点的树,每条边 $i$ 有权值 $w_i$ 。XHRlyb是个好奇宝宝,她想知道Icefox的树上点 $u$ 与点 $v$ 之间的路径上的所有边的权值异或和是多少,算数和是多少。你可以帮帮她吗?因为今天是愚人节,所以XHRlyb会进行 $m$ 次询问。

输入格式

第一行两个正整数 $n,m$ , 分别表示点数和询问数。

接下来 $n-1$ 行,每行三个整数 $x,y,w$ , 表示一条权值为 $w$ 的边连接点 $x$ 和点 $y$ , 数据保证给出的图是一棵树。

接下来 $m$ 行,每行有三个整数 $op,u,v$ ,表示一次询问。

  • $op=0$ ,询问异或和。
  • $op=1$ ,询问算数和。

输出格式

对于每个询问输出一行一个整数,表示答案。

样例输入

text 5 5 1 2 3 2 4 5 2 5 6 1 3 2 0 1 4 1 1 4 0 4 3 1 4 3 0 1 1

样例输出

text 6 8 4 10 0

数据范围

对于 10% 的数据,$2\leq n\leq 10$, $2\leq m\leq 10$, $0\leq w_i\leq10^3$

对于 30% 的数据,$2\leq n\leq 1000$, $2\leq m\leq 1000$, $0\leq w_i\leq10^3$

对于 另外 20% 的数据,$n=9999$, $2\leq m\leq10^5$, $0\leq w_i\leq10^3$ , 保证数据是一条$1->2->...->i->i+1->...->n$链

对于 另外 30% 的数据,$2\leq n\leq 10^5$, $2\leq m\leq 10^5$, $0\leq w_i\leq10^3$ , 保证所有的询问 $op=0$

对于 100% 的数据,保证 $2\leq n\leq 10^5$, $2\leq m\leq10^5$, $0\leq w_i\leq10^3$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!