题解
- 这题我是用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
",f1[x],f2[x]);
37 }
38 }