【bzoj2631】tree

2014年8月8日4,21511

Description

 一棵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的余数。

Input

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

Output

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

Sample Input

3 2
1 2
2 3
* 1 3 4
/ 1 1

Sample Output

4

HINT

数据规模和约定
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

题解

其实这题不需要开long long。。。只要unsigned int,不然可能会T

 

  • 吴钰晗2015年4月15日 下午7:45 回复

    “其实这题不需要开long long。。。只要unsigned int,不然可能会T”是可怕

    #1  
  • 涵丶2015年4月19日 上午10:12 回复

    为什么这个地方不用dfs而是一个一个link就行?

    #2  
    • hzwer2015年4月30日 上午11:09 回复
      admin

      随意QAQ

      #21
  • A72015年4月30日 上午9:48 回复

    6 1
    1 2
    2 3
    3 4
    1 5
    4 6
    / 4 5
    这组数据好像不大对啊0.0,为什么输出了3?(好像是5)

    #3  
    • hzwer2015年4月30日 上午10:50 回复
      admin

      已更正

      #31
  • 小蒟蒻2016年2月17日 下午8:58 回复

    黄学长,请问您写的LCT如何处理有根树的问题?

    #4  
  • 小蒟蒻2016年2月17日 下午9:17 回复

    黄学长,请问isroot()能不能这样判断:
    bool isroot(int x) { return fa[ x ] > 0; }

    #5  
    • hzwer2016年2月18日 上午12:09 回复
      admin

      不可以,lct维护的一堆splay中,只有1棵splay的根是0,其余的根指向上一条重边。
      还有你说的有根树不会有什么问题吧。

      #51
      • 小蒟蒻2016年2月18日 下午12:38 回复

        可是您打了一个rev标记,那就是说每次makeroot()之后节点相对深度都会改变,根节点不会随之变化吗?

        #52
  • 李天逸2017年3月18日 上午8:58 回复

    黄学长,请问cut的时候为什么不需要update?

    #6