[bfs] Jzoj P3797 签到题3

冷不防 2021-12-10 08:37 320阅读 0赞

#### Description ####

给定一棵有根树（根节点为1），每个点都带有权值，对于点u，其权值设为a\[u\]，其父亲为fa\[i\]。现有两个函数f1,f2，定义如下：  
如果u=1，f1\[u\]=a\[u\],f2\[u\]=1  
否则  
如果f1\[fa\[u\]\]+1<a\[u\] f1\[u\]=a\[u\],f2\[u\]=1;  
如果f1\[fa\[u\]\]+1>a\[u\] f1\[u\]=f1\[fa\[u\]\]+1,f2\[u\]=f2\[fa\[u\]\]  
如果f1\[fa\[u\]\]+1=a\[u\] f1\[u\]=f1\[fa\[u\]\]+1,f2\[u\]=f2\[fa\[u\]\]+1  
现在有两种操作：  
0 u val 表示将a\[u\]改成val  
1 u 表示查询f1\[u\]和f2\[u\]

#### Input ####

第一行为n。第二行为n个正整数，第i个数代表第i个点初始时的权值a\[i\]。接下来n-1行，每行两个整数u,v，代表u与v连有一条边。接下来一行为一个正整数Q。下面Q行，每一行格式为0 u val 或1 u。

#### Output ####

对于每种格式为1 u的询问，输出一行两个数，分别为f1\[u\],f2\[u\]

#### Sample Input ####

3
    1 2 3
    1 2
    2 3
    1
    1 3

#### Sample Output ####

3 3

#### Data Constraint ####

对于40%的数据 n<=1000,Q<=1000  
对于另外40%的数据 保证这棵树为一条链  
对于100%的数据 n<=200000,Q<=200000

# 题解 #

*  这题我是用bfs水过去的，**有点优秀 （又短又快）**
 *  先bfs将整棵树的所有f1,f2数组给求出来，然后每次修改就从该点往它的子树里跑，边跑边修改
 *  至于赋值的话，就直接按照上面的关系打就好了
 *  
 *  正解是**树链剖分**
 *  题目给出的f1,f2函数就是在求从根节点到某个结点的最大值以及最大值出现的次数
 *  那么就树剖套上线段树就好了

# 代码 #

1 #include <cstdio>
     2 #include <iostream>
     3 using namespace std;
     4 const int N=500010;
     5 int cnt,n,q,head,tail,state[N],a[N],f1[N],f2[N],fa[N],last[N];
     6 struct edge{
        int to,from;}e[N*2];
     7 void insert(int x,int y)
     8 {
     9     e[++cnt].to=y,e[cnt].from=last[x],last[x]=cnt;
    10     e[++cnt].to=x,e[cnt].from=last[y],last[y]=cnt;
    11 }
    12 void bfs(int x)
    13 {
    14     head=0,tail=1,state[1]=x;
    15     while (head<tail)
    16     {
    17         x=state[++head];
    18         int p1=f1[x],p2=f2[x];
    19         if (x==1) f1[x]=a[x],f2[x]=1;
    20         else if (f1[fa[x]]+1<a[x]) f1[x]=a[x],f2[x]=1;
    21         else if (f1[fa[x]]+1>a[x]) f1[x]=f1[fa[x]]+1,f2[x]=f2[fa[x]];
    22         else if (f1[fa[x]]+1==a[x]) f1[x]=f1[fa[x]]+1,f2[x]=f2[fa[x]]+1;
    23         if (p1==f1[x]&&p2==f2[x]) continue;
    24         for (int i=last[x];i;i=e[i].from) if (e[i].to!=fa[x]) fa[e[i].to]=x,state[++tail]=e[i].to;
    25     }
    26 }
    27 int main()
    28 {
    29     scanf("%d",&n);
    30     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    31     for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),insert(x,y);
    32     bfs(1),scanf("%d",&q);
    33     for (int op,x,y;q;q--)
    34     {
    35         scanf("%d%d",&op,&x);
    36         if (op==0) scanf("%d",&y),a[x]=y,bfs(x); else printf("%d %d\n",f1[x],f2[x]);
    37     } 
    38 }

转载于:https://www.cnblogs.com/Comfortable/p/11125153.html