【bzoj3551】[ONTAK2010]Peaks加强版

2014年8月30日3,5612

Description

【题目描述】同3545

Input

第一行三个数N,M,Q。
第二行N个数,第i个数为h_i
接下来M行,每行3个数a b c,表示从a到b有一条困难值为c的双向路径。
接下来Q行,每行三个数v x k,表示一组询问。v=v xor lastans,x=x xor lastans,k=k xor lastans。如果lastans=-1则不变。

Output

同3545

HINT

【数据范围】同3545

题解

本题强制在线。。。

据出题人的做法。。。

就是做最小生成树,但合并两结点x,y的时新建结点ext,把ext连向fa(x),fa(y)这样建出一棵树,ext的权为该边的边权

找一个点v不超过x的子树的根,可以用倍增,以它为根的子树就是v不超过x所能到达的连通块

dfs+主席树就行了。。

 

  • kekeda2016年3月1日 下午8:39 回复

    mx[x][i]=max(mx[x][i-1],mx[fa[x][i-1]][i-1]); 第五十三行的这条语句需要max吗?Kruskal重构树不是满足deep小的权值大吗

    #1  
    • hzwer2016年3月1日 下午9:46 回复
      admin

      你说的有道理,我当时并没有注意,就按照通常的做法写了

      #11