HihoCoder1576 子树中的最小权值( dfs序 +线段树 || 树剖)

给定一棵N个节点的树，编号1~N。其中1号节点是根，并且第i个节点的权值是V_i。

针对这棵树，小Hi会询问小Ho一系列问题。每次小Hi会指定一个节点x，询问小Ho以x为根的子树中，最小的权值是多少。为了增加难度，小Hi可能随时改变其中每个节点的权值。

你能帮助小Ho准确、快速的回答小Hi的问题吗？

Input

第一行一个正整数N。

第二行N个整数，V₁, V₂, ... V_N。

第三行n-1个正整数，第i个数P_i表示第i+1号节点的父结点是第P_i号节点。注意1号节点是根。

第四行一个正整数Q，表示有Q个询问/修改权值。

接下来Q行，每行可能有如下两种输入格式：

1 x u

2 x

第一种表示将第x号节点的权值修改为u

第二种表示询问以第x号节点为根的子树中，最小的权值是多少。

对于30%的数据，1 ≤ N, Q ≤ 1000

对于100%的数据，1 ≤ N, Q ≤ 100000, -10⁹ <= V_i, u <= 10⁹

Output

对于每次询问，输出一个整数表示答案。

Sample Input

12
3 5 -1 -2 9 6 2 8 -10 11 8 10
1 1 1 2 4 2 6 7 7 8 8
10
2 3
2 1
2 6
1 11 -5
1 5 -12
2 6
2 4
2 2
2 1
2 7

Sample Output

-1
-10
6
-5
-5 
-12
-12
-10

求子树的最小值。单点更新。显然是dfs序，然后按顺序存入线段树里面，由于一颗子树在线段树里的位置相邻，我们可以利用起线段树。

没必要写树剖。由于今天做的几道XOR题太难，我已经疯了。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=400010;
int sa[maxn],Rank[maxn];
int Laxt[maxn],Next[maxn],To[maxn],cnt;
int fa[maxn],a[maxn],sz[maxn],tot=1;
int ch[maxn][2],Min[maxn];
void add(int u,int v)
{
    Next[++cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
}
int dfs(int u)
{
    sz[u]=1;
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        sa[v]=++tot;
        Rank[tot]=v;
        sz[u]+=dfs(v);
    } return sz[u];
}
void update(int Now)
{
    Min[Now]=min(Min[Now<<1],Min[Now<<1|1]);
}
void build(int Now,int L,int R)
{
    if(L==R) { Min[Now]=a[Rank[L]]; return ;}
    int Mid=(L+R)>>1;
    build(Now<<1,L,Mid);
    build(Now<<1|1,Mid+1,R);
    update(Now);
}
int query(int Now,int L,int R,int l,int r)
{
    if(l<=L&&r>=R) return Min[Now];
    int Mid=(L+R)>>1;
    if(r<=Mid) return query(Now<<1,L,Mid,l,r);
    else if(l>Mid) return query(Now<<1|1,Mid+1,R,l,r);
    else return min(query(Now<<1,L,Mid,l,Mid),query(Now<<1|1,Mid+1,R,Mid+1,r));
}
void change(int Now,int L,int R,int x,int val)
{
    if(L==R) { Min[Now]=val;return ;}
    int Mid=(L+R)>>1;
    if(x<=Mid) change(Now<<1,L,Mid,x,val);
    else change(Now<<1|1,Mid+1,R,x,val); 
    update(Now);
}
int main()
{
     int i,j,n,q,x,y,opt;
     scanf("%d",&n);
     for(i=1;i<=n;i++) scanf("%d",&a[i]);
     for(i=2;i<=n;i++) scanf("%d",&fa[i]),add(fa[i],i);
     sa[1]=1; Rank[1]=1; dfs(1); build(1,1,n);
     scanf("%d",&q);
     for(i=1;i<=q;i++){
         scanf("%d",&opt);
         if(opt==1) scanf("%d%d",&x,&y),change(1,1,n,sa[x],y);
         else {
            scanf("%d",&x);
            printf("%d
",query(1,1,n,sa[x],sa[x]+sz[x]-1));
        }
     } 
     return 0;
}