/****************************************\
* Author : ztx
* Title : tsinsen A1506. Missing On The Tree（张闻涛）
* ALG : LCT
* CMT : 推荐题解 http://ezreal-dn.com/archives/124
* 第一行一个数n 表示节点个数
* 第2到n行，每行一个数x，第i行的x表示i节点的父亲为x
* 接下来一个数m，表示操作与询问个数的总和
* 接下来m行，每行的开头有1个数p
* 若p为0，则接下来有2个数x，y，表示将x号节点的权值加上y
* 若p为1，则接下来有3个数x，y，z，表示将x号节点到y号节点的这条链上的每个节点的权值加上z
* 若p为2，则接下来有2个数x，y，表示将以x号节点为根的子树的每个节点的权值加上z
* 若p为3，则接下来有2个数x，y，表示询问x号节点到y号节点的这条链上每个节点的权值和，你需要输出这个和
* 若p为4，则接下来有2个数x，y，表示询问x号节点到y号节点的这条链上每个节点的权值的最大值，你需要输出这个最大值
* 若p为5，则接下来有2个数x，y，表示将x号节点的父亲改为y号节点
* Time :
\****************************************/
/****************************************\
* Author : ztx
* Title : tsinsen A1506. Missing On The Tree（张闻涛）
* ALG : LCT
* CMT : 推荐题解 http://ezreal-dn.com/archives/124
* 第一行一个数n 表示节点个数
* 第2到n行，每行一个数x，第i行的x表示i节点的父亲为x
* 接下来一个数m，表示操作与询问个数的总和
* 接下来m行，每行的开头有1个数p
* 若p为0，则接下来有2个数x，y，表示将x号节点的权值加上y
* 若p为1，则接下来有3个数x，y，z，表示将x号节点到y号节点的这条链上的每个节点的权值加上z
* 若p为2，则接下来有2个数x，y，表示将以x号节点为根的子树的每个节点的权值加上z
* 若p为3，则接下来有2个数x，y，表示询问x号节点到y号节点的这条链上每个节点的权值和，你需要输出这个和
* 若p为4，则接下来有2个数x，y，表示询问x号节点到y号节点的这条链上每个节点的权值的最大值，你需要输出这个最大值
* 若p为5，则接下来有2个数x，y，表示将x号节点的父亲改为y号节点
* Time :
\****************************************/
#include <cstdio>
#include <cstring>
int CH , NEG ;
inline void read(int& ret) {
ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
if (CH == '-') NEG = true , CH = getchar() ;
while (ret = (ret<<1)+(ret<<3)+CH-'0' , CH=getchar() , CH>'!') ;
if (NEG) ret = -ret ;
}
#define maxn 50010LL
#define max(a,b) ((a)>(b)?(a):(b))
#define infi 0x3f3f3f3fLL
int fa[maxn] = {0} , ch[maxn][2] = {0} ;
int val[maxn] = {0} , vir[maxn] = {0} ;/* u的值，与u相连的虚边的增值 */
int add[maxn] = {0} , chadd[maxn] = {0} ;/* val的标记，vir的标记 */
int size[maxn] = {0} , sum[maxn] = {0} , maxv[maxn] = {0} ;
#define null 0LL
#define left(u) ch[u][0]
#define right(u) ch[u][1]
inline bool Isrt(int u) {
return (!fa[u]) || ((left(fa[u])!=u)&&(right(fa[u])!=u)) ;
}
inline void Maintain(int u) {
size[u] = 1 , sum[u] = maxv[u] = val[u] ;
if (left(u)) {
size[u] += size[left(u)] ;
sum[u] += sum[left(u)] ;
maxv[u] = max(maxv[left(u)] , maxv[u]) ;
}
if (right(u)) {
size[u] += size[right(u)] ;
sum[u] += sum[right(u)] ;
maxv[u] = max(maxv[right(u)] , maxv[u]) ;
}
}
inline void Add(int u , int w) {
if (u) {
val[u] += w ;
sum[u] += size[u]*w ;
maxv[u] += w ;
add[u] += w ;
}
}
inline void ChAdd(int u , int w) {
if (u) {
vir[u] += w ;
chadd[u] += w ;
}
}
inline void Clear(int u) {
if (u) {
if (add[u])
Add(left(u) , add[u]) ,
Add(right(u) , add[u]) ,
add[u] = 0 ;
if (chadd[u])
ChAdd(left(u),chadd[u]) ,
ChAdd(right(u),chadd[u]) ,
chadd[u] = 0 ;
}
}
inline void zig(int x) {
/* right rotate */
int y = fa[x] , z = fa[y] ;
if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
fa[right(x)] = y ; left(y) = right(x) ; fa[y] = x ; right(x) = y ;
Maintain(y) ;
}
inline void zag(int x) {
/* left rotate */
int y = fa[x] , z = fa[y] ;
if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
fa[left(x)] = y ; right(y) = left(x) ; fa[y] = x ; left(x) = y ;
Maintain(y) ;
}
inline void Splay(int x) {
Clear(x) ;
int y , z ;
while (!Isrt(x)) {
y = fa[x] , z = fa[y] ;
if (Isrt(y)) {
Clear(y) , Clear(x) ;
if (left(y) == x) zig(x) ; else zag(x) ;
} else {
Clear(z) , Clear(y) , Clear(x) ;
if (left(z) == y) {
if (left(y) == x) zig(x) , zig(x) ;
else zag(x) , zig(x) ;
} else if (right(z) == y) {
if (right(y) == x) zag(x) , zag(x) ;
else zig(x) , zag(x) ;
}
}
}
Maintain(x) ;
}
inline int Access(int u) {
int v = null ;
for ( ; u ; u = fa[u]) {
Splay(u) ;
if (v) Add(v,vir[u]) , ChAdd(v,vir[u]) ;
if (right(u)) Add(right(u),-vir[u]) , ChAdd(right(u),-vir[u]) ;
right(u) = v , v = u ; Maintain(u) ;
}
return v ;
}
inline int LCA(int u , int v) {
Access(u) ; return Access(v) ;
}
inline void Cut(int u) {
Access(u) , Splay(u) ;
fa[left(u)] = null ; left(u) = null ;
}
inline void Link(int u , int v) {
Access(v) ;
Splay(u) , fa[u] = v ;
if (vir[v]) ChAdd(u,-vir[v]) ;
if (vir[v]) Add(u,-vir[v]) ;
Access(u) ;
}
void NodeAdd(int u , int w) {
Access(u) , Splay(u) ; val[u] += w ;
}
void ChainAdd(int u , int v , int w) {
Access(v) ;
for (v = null ; u ; u = fa[u]) {
Splay(u) ;
if (v) Add(v,vir[u]) , ChAdd(v,vir[u]) ;
/*虚边变实边*/
if (!fa[u]) Add(v,w) , Add(right(u),w) , val[u] += w ;
/*打标记*/
if (right(u)) Add(right(u),-vir[u]) , ChAdd(right(u),-vir[u]) ;
/*实边变虚边*/
right(u) = v , v = u ; Maintain(u) ;
}
}
void SubtreeAdd(int u , int w) {
Access(u) , Splay(u) ;
val[u] += w , vir[u] += w ;
}
void ChainSum(int u , int v) {
Access(v) ;
for (v = null ; u ; u = fa[u]) {
Splay(u) ;
if (v) Add(v,vir[u]) , ChAdd(v,vir[u]) ;
if (!fa[u]) printf("%d\n",val[u]+sum[v]+sum[right(u)]) ;
if (right(u)) Add(right(u),-vir[u]) , ChAdd(right(u),-vir[u]) ;
right(u) = v , v = u ; Maintain(u) ;
}
}
void ChainMax(int u , int v) {
Access(v) ;
for (v = null ; u ; u = fa[u]) {
Splay(u) ;
if (v) Add(v,vir[u]) , ChAdd(v,vir[u]) ;
if (!fa[u]) printf("%d\n",max(max(val[u],maxv[v]),maxv[right(u)])) ;
if (right(u)) Add(right(u),-vir[u]) , ChAdd(right(u),-vir[u]) ;
right(u) = v , v = u ; Maintain(u) ;
}
}
void ChangeFather(int u , int v) {
if (LCA(u,v)==u) return ;
Cut(u) , Link(u,v) ;
}
int n , cmd , u , v , w , Q ;
int main() {
// #define READ
#ifdef READ
freopen(".in" ,"r",stdin ) ;
freopen(".out","w",stdout) ;
#endif
read(n) ;
for (u = 2 ; u <= n ; u ++ ) {
read(v) ; fa[u] = v ;
}
for (u = 1 ; u <= n ; u ++ ) size[u] = 1 ;
val[null] = maxv[null] = -infi ; sum[null] = 0 ;
read(Q) ;
while ( Q -- ) {
read(cmd) , read(u) , read(v) ;
if (cmd == 0) NodeAdd(u , v) ;
else if (cmd == 1) read(w) , ChainAdd(u , v , w) ;
else if (cmd == 2) SubtreeAdd(u , v) ;
else if (cmd == 3) ChainSum(u , v) ;
else if (cmd == 4) ChainMax(u , v) ;
else if (cmd == 5) ChangeFather(u , v) ;
}
#ifdef READ
fclose(stdin) ; fclose(stdout) ;
#else
getchar() ; getchar() ;
#endif
return 0 ;
}
/*
3
1
1
2
1 2 3 -1
3 2 3
*/
评论 (0)