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]=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
The Solution
先来讲讲我的方法吧（水法）
首先一开始拿到这道题，而且还放在第三个位置，心里有点虚，就没有多想，以为是不可做的。但敲完前面的 题后，无聊的我玩笔头，刷页面，回去再仔细看看这道题，发现好像暴力挺好打的！！
眼睛一亮，开始暴力~~~
我们可以以1号节点为根节点，先暴力Dfs走一遍，顺便开个Fa数组记录当前结点的父亲是什么。对于修改权值这操作，我们再把权值改一改，再跑一遍Dfs，里面做一下题目要求我们做的事情就好了。
只是抱着侥幸心理交了上去却能AC，我也是醉了。。。
而且还跑得飞起，比正解快多了(偷笑.jpg)
好了讲一下正解
链剖
树链剖分，维护区间最大值，对于一个点X,它有一个祖先Y，那么点Y对于点X的f1影响是a[y]+(deep[x]-deep[y]),实际上f1就是求一个点到树根的链上，最大的值，f2就是求最大的值有多少个。
然后对与每个点I，修改操作就是把A[Y]-DEEP[Y]修改线段树中对应区间，这是LOG的。查询操作，则通过树链剖分，求最优值，这也是LOG的
Orz各位大爷。
下面附上我的代码（虽然是暴力，但也是飞起的！！）
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#define fo(i,a,b) for (int i=a;i<=b;i++)
#define fd(i,a,b) for (int i=a;i>=b;i--)
#define N 200005
using namespace std;
int read(int &n)
{
char ch = ' ';
int q = 0, w = 1;
for (;(ch != '-') && ((ch < '0') || (ch> '9'));ch = getchar());
if (ch == '-') w = -1,ch = getchar();
for (; ch >= '0' && ch <= '9';ch = getchar()) q = q * 10 + ch - 48;
n = q * w;
return n;
}
int a[N],Final[N],f1[N],f2[N],Fa[N],d[N];
int tot = 0;
struct Edge
{
int to,next;
Edge(void){}
Edge(int a,int b) : to(a),next(b){}
}E[N * 2];
void Link(int x,int y)
{
E[++ tot] = Edge(y,Final[x]),Final[x] = tot;
E[++ tot] = Edge(x,Final[y]),Final[y] = tot;
}
void Query(int x)
{
int xx = Fa[x];
if (x == 1) f1[x] = a[x],f2[x] = 1;
else
{
if (f1[xx] + 1 < a[x]) f1[x] = a[x],f2[x] = 1;
else if (f1[xx] + 1 > a[x]) f1[x] = f1[xx] + 1,f2[x] = f2[xx];
else if (f1[xx] + 1 == a[x]) f1[x] = f1[xx] + 1,f2[x] = f2[xx] + 1;
}
}
void Dfs(int x)
{
int l = 0,r = 1;
d[1] = x;
while (l < r)
{
x = d[++ l];
int x1 = f1[x],
x2 = f2[x];
Query(x);
if (x1 == f1[x] && x2 == f2[x]) continue;
for (int k = Final[x];k;k = E[k].next)
if (E[k].to != Fa[x])
{
Fa[E[k].to] = x;
d[++ r] = E[k].to;
}
}
}
int main()
{
int n;
read(n);
fo(i,1,n) read(a[i]);
fo(i,1,n - 1)
{
int x,y;
read(x),read(y);
Link(x,y);
}
int Q,typ,x,val;
read(Q);
Fa[1] = 0;
Dfs(1);
while (Q --)
{
read(typ);
if (typ == 0)
{
read(x),read(val);
a[x] = val;
Dfs(x);
}
else
if (typ == 1)
{
read(x);
printf("%d %d\n",f1[x],f2[x]);
}
}
} 附上大佬的链剖AC代码
type
point=^node;
node=
record
x:longint;
next:point;
end;
var
n,q,i,x,y:longint;
a,f1,f2,fa:array[0..200000]of longint;
h,h1:array[1..200000]of point;
pd:array[1..200000]of boolean;
procedure inse(x,y:longint);
var
p:point;
begin
new(p);
p^.x:=y;
p^.next:=h1[x];
h1[x]:=p;
end;
procedure inse1(x,y:longint);
var
p:point;
begin
new(p);
p^.x:=y;
p^.next:=h[x];
h[x]:=p;
end;
procedure dfs(x:longint);
var
p:point;
begin
if f1[fa[x]]+1<a[x] then
begin
f1[x]:=a[x];
f2[x]:=1;
end;
if f1[fa[x]]+1>a[x] then
begin
f1[x]:=f1[fa[x]]+1;
f2[x]:=f2[fa[x]];
end;
if f1[fa[x]]+1=a[x] then
begin
f1[x]:=f1[fa[x]]+1;
f2[x]:=f2[fa[x]]+1;
end;
pd[x]:=true;
p:=h1[x];
while p<>nil do
begin
if not pd[p^.x] then
begin
inse1(x,p^.x);
fa[p^.x]:=x;
dfs(p^.x);
end;
p:=p^.next;
end;
end;
procedure change(x:longint);
var
p:point;
x1,y1:longint;
begin
x1:=f1[x];
y1:=f2[x];
if f1[fa[x]]+1<a[x] then
begin
f1[x]:=a[x];
f2[x]:=1;
end;
if f1[fa[x]]+1>a[x] then
begin
f1[x]:=f1[fa[x]]+1;
f2[x]:=f2[fa[x]];
end;
if f1[fa[x]]+1=a[x] then
begin
f1[x]:=f1[fa[x]]+1;
f2[x]:=f2[fa[x]]+1;
end;
if (f1[x]=x1)and(f2[x]=y1)then exit;
p:=h[x];
while p<>nil do
begin
change(p^.x);
p:=p^.next;
end;
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n-1do
begin
readln(x,y);
inse(x,y);
inse(y,x);
end;
f1[0]:=-maxlongint;
dfs(1);
readln(q);
for i:=1 to q do
begin
read(x);
if x=1 then
begin
readln(x);
writeln(f1[x],' ',f2[x]);
end
else
begin
readln(x,y);
a[x]:=y;
change(x);
end;
end;
end.