P3401 洛谷树

    • 91通过
    • 279提交
  • 题目提供者 Created_equal1 管理员
  • 评测方式 云端评测
  • 标签 树链剖分,树剖 线段树 洛谷原创 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    萌哒的Created equal小仓鼠种了一棵洛谷树!

    (题目背景是辣鸡小仓鼠乱写的QAQ)。

    题目描述

    树是一个无环、联通的无向图,由n个点和n-1条边构成。树上两个点之间的路径被定义为他们之间的唯一一条简单路径——显然这是一条最短路径。

    现在引入一个概念——子路径。假设树上两个点p1和pn之间的路径是P=<p1,p2,p3,…,pn>,那么它的子路径被定义为某一条路径P’,满足P’=<pi,pi+1,pi+2,…,pj>,其中1<=i<=j<=n。显然,原路径是一条子路径,任意一个点也可以作为子路径。

    我们给每条边赋予一个边权。萌萌哒的Sugar问小仓鼠:对于任意两个点u和v,你能快速求出,u到v的路径上所有子路径经过的边的边权的xor值的和是多少。具体地说就是,你把u到v的路径上所有子路径全部提出来,然后分别把每个子路径上经过的边的边权xor在一起,最后求出得到的所有xor值的和。

    什么?你不知道xor?那就去百度啊!

    这时候,fjzzq2002大爷冒了粗来:窝还要你滋磁修改某条边边权的操作!

    小仓鼠那么辣鸡,当然不会做这道题啦。于是他就来向你求救!

    输入输出格式

    输入格式:

    第一行两个正整数n和q,表示点的个数,查询和询问的总次数。

    接下来n-1行,每行两个正整数u、v、w,表示u和v两个点之间有一条边权为w的边。

    接下来q行,格式为1 u v或2 u v w。如果为1 u v操作,你需要输出u到v的路径上所有子路径经过的边的边权的xor值的和是多少;如果为2 u v w操作,你需要把u到v这条边的边权改为w,保证这条边存在。

    输出格式:

    对于每个1操作,输出答案。

    输入输出样例

    输入样例#1: 复制
    5 3
    1 2 3
    2 3 3
    2 4 6
    4 5 1
    1 3 4
    2 2 4 7
    1 3 5
    输出样例#1: 复制
    14
    26
    

    说明

    __本题时限1s,内存限制128M,因新评测机速度较为接近NOIP评测机速度,请注意常数问题带来的影响。__

    【数据范围】

    No    n=    q=    备注
    1    100    5    无
    2    100    20    无
    3    100    100    无
    4    5000    1000    无
    5    5000    2000    无
    6    5000    3000    无
    7    10000    10000    第i条边连接第i个点和第i+1个点,且没有2操作
    8    10000    20000    第i条边连接第i个点和第i+1个点,且没有2操作
    9    10000    10000    第i条边连接第i个点和第i+1个点
    10    10000    20000    第i条边连接第i个点和第i+1个点
    11    10000    10000    没有2操作
    12    10000    20000    没有2操作
    13    20000    20000    没有2操作
    14    30000    30000    没有2操作
    15    30000    10000    无
    16    20000    20000    无
    17    20000    20000    无
    18    30000    20000    无
    19    20000    30000    无
    20    30000    30000    无

    对于100%的数据,所有边权小于等于1023。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。