P1501 [国家集训队]Tree II

    • 331通过
    • 792提交
  • 题目提供者 JOHNKRAM
  • 评测方式 云端评测
  • 标签 Link-Cut Tree,LCT WC/CTSC/集训队
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms / 512MB

题解

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

    推荐的相关题目 显示

    题目描述

    一棵n个点的树,每个点的初始权值为1。对于这棵树有q个操作,每个操作为以下四种操作之一:

    • + u v c:将u到v的路径上的点的权值都加上自然数c;

    • - u1 v1 u2 v2:将树中原有的边(u1,v1)删除,加入一条新边(u2,v2),保证操作完之后仍然是一棵树;

    • \* u v c:将u到v的路径上的点的权值都乘上自然数c;

    • / u v:询问u到v的路径上的点的权值和,求出答案对于51061的余数。

    输入输出格式

    输入格式:

    第一行两个整数n,q

    接下来n-1行每行两个正整数u,v,描述这棵树

    接下来q行,每行描述一个操作

    输出格式:

    对于每个/对应的答案输出一行

    输入输出样例

    输入样例#1: 复制
    3 2
    1 2
    2 3
    * 1 3 4
    / 1 1
    输出样例#1: 复制
    4
    

    说明

    10%的数据保证,1<=n,q<=2000

    另外15%的数据保证,1<=n,q<=5*10^4,没有-操作,并且初始树为一条链

    另外35%的数据保证,1<=n,q<=5*10^4,没有-操作

    100%的数据保证,1<=n,q<=10^5,0<=c<=10^4

    By (伍一鸣)

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