一道 2800，做了一个月。

首先题目给了我们极好的提示，是让我们求半径的最小值。此时我们就可以考虑将其转化为直径，定义一棵树的直径 $d=\max{a_u+a_v+d_v(v)}$。

此时半径 $r=\lceil\frac{d}{2}\rceil$。

证明较为显然且其他题解均有较为详细的证明，所以故不再赘述。

现在的问题转化为了求 $d$。

考虑修改对 $d$ 的影响，设原直径端点为 $u,v$，当 $d_x$ 修改的变化量 $\Delta\ge0$ 时，直径的端点取值只能为 $(u,x),(v,x),(x,x)$ 或者不变。

当 $d_x$ 修改的变化量 $\Delta<0$ 时，发现直径端点的变化不确定，此时就比较难做。

此时我们考虑令所有的点的初始值均为 $0$，可以使用线段树分治，此时相当于所有修改都是从 $0$ 开始的，故变化量都大于 $0$。

详情见代码，时间复杂度$O(n\log^2n)$。

code

#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
using namespace std;
struct sss
{
    int q,w,nxt;
}a[500005];
void update(pii);
int ans[200005],S,T,Dis,s[200005];
struct Segment_Tree
{
    struct sss
    {
        int l,r;
        vector<pii>v;
        #define l(x) tree[x].l
        #define r(x) tree[x].r
        #define v(x) tree[x].v
    }tree[2000005];
    void build(int x,int l,int r)
    {
        l(x)=l;r(x)=r;
        if(l(x)==r(x))return;
        int mid=(l+r)>>1;
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
    }
    void change(int x,int l,int r,pii p)
    {
        if(l<=l(x)&&r(x)<=r)return v(x).push_back(p);
        int mid=(l(x)+r(x))>>1;
        if(l<=mid)change(x*2,l,r,p);
        if(mid<r)change(x*2+1,l,r,p);
    }
    void dfs(int x)//线段树分治
    {
        for(pii x:v(x))update(x);
        if(l(x)==r(x))ans[l(x)]=(Dis+1)/2;//记录答案
        else
        {
            int ns=S,nt=T,nd=Dis;
            dfs(x*2);
            S=ns,T=nt,Dis=nd;//回溯
            dfs(x*2+1);
        }
        for(pii x:v(x))s[x.first]=0;//把值都清空为 0
    }
}T1;
int head[1000005],cnt,n,p[200005][21],d[200005],Q,vis[200005],lst[200005];
void adde(int q,int w)
{
    a[++cnt].q=q;
    a[cnt].w=w;
    a[cnt].nxt=head[q];
    head[q]=cnt;
}
int LCA(int x,int y)
{
    if(d[x]<d[y])swap(x,y);
    for(int i=20;i>=0;i--)if(d[p[x][i]]>=d[y])x=p[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--)if(p[x][i]!=p[y][i])x=p[x][i],y=p[y][i];
    return p[x][0];
}
int dis(int x,int y){return d[x]+d[y]-2*d[LCA(x,y)];}
void update(pii p)
{
    int x=p.first;
    s[x]=p.second;//因为 s[x] 已经被清空为 0，所以可以直接使用变化量大于 0 的结论
    int ns=S,nt=T,nD=Dis;
    vector<pii>cds={ {S,x},{x,T},{x,x} };//新的值只会在这三种出现
    for(auto &y:cds)
    {
        int d1=dis(y.first,y.second);
        if(nD<s[y.first]+d1+s[y.second])
        {
            nD=s[y.first]+d1+s[y.second];
            ns=y.first,nt=y.second;
        }
    }
    S=ns;
    T=nt;
    Dis=nD;
}
void dfs(int x,int fa)
{
    p[x][0]=fa;
    d[x]=d[fa]+1;
    for(int i=1;i<=20;i++)p[x][i]=p[p[x][i-1]][i-1];
    for(int i=head[x];i;i=a[i].nxt)if(a[i].w^fa)dfs(a[i].w,x);
}
int findD(int S)//预处理直径
{
    memset(vis,0,sizeof(vis));
    queue<int> q;
    vis[S]=1;
    q.push(S);
    int x;
    while(!q.empty())
    {
        x=q.front(); 
        q.pop();
        for(int i=head[x];i;i=a[i].nxt)
        {
            if(vis[a[i].w])continue;
            vis[a[i].w] = 1;
            q.push(a[i].w);
        }
    }
    return x;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&s[i]);
    for(int i=1;i<n;i++)
    {
        int q,w;
        scanf("%d%d",&q,&w);
        adde(q,w);
        adde(w,q);
    }
    dfs(1,0);
    S=findD(1);
    T=findD(S);
    Dis=dis(S,T);
    scanf("%d",&Q);
    T1.build(1,1,Q+1);
    for(int i=2;i<=Q+1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        T1.change(1,lst[x],i-1,mp(x,s[x]));//将修改加入至线段树
        lst[x]=i;
        s[x]=y;
    }
    for(int i=1;i<=n;i++)T1.change(1,lst[i],Q+1,mp(i,s[i]));
    memset(s,0,sizeof(s));
    T1.dfs(1);
    for(int i=2;i<=Q+1;i++)printf("%d\n",ans[i]);
}