1.题目大意:

时隔六日,爷终于会了,不就是点分树吗?(有手就行..咦,不对,我手呢?)
来看看这个题目,这个题目是说你有一颗树啊.
然后两个操作.
第一个操作是:
查询u距离不超过k的点权和.
第二个操作是:
修改u的点权.


2.解题思路:

很快啊,大佬很快就会做了,我大意了,看了三天.原来大佬是有备(动态开点)而来.
正题:
首先在学点分树前先学动态开点,lca,虚树,点分治,容斥.学完这些学这个算法就很简单了.因为这个算法就是这些算法的集合.对于这个题目的步骤如下:
1.先dfs一下,处理原树的深度.和预处理f[i][j]倍增数组,表示i这个点,2^j上是哪个点,这里我们拿1当作根节点.然后搜一下就完事.
2.寻找重心.这里同点分治寻找重心是一样的.
3.然后建立一颗虚数,这里同点分治的solve过程类似.虚数的话,你只要开一个dfa[u]表示u的虚数的父节点是哪个就好了.
4.下面就是重点了,我们建一个动态开点的线段树,具体作用是:单点更新,区间查询前缀和的作用.我们对于每个点都开两个线段树(线段树的下标就是距离其他点与这个点的距离,线段树的权值则是点权).第一颗线段树维护的是:虚数下在这个点的节点对于虚数上的点u的贡献(一直可表达到根).第二颗线段树维护的是:虚数上这个点的节点对于它的爷爷dfa[u]的贡献(一直可表达到根).然后由容斥原理可以简单的得到,我这个点的贡献就是第一颗线段树中的贡献-第二颗线段树的贡献.然后就没了~
(确信没讲废话...然后就是手撸代码了)


3.代码

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+3e4,M=19;
int val[N],dep[N],f[N][M];
vector<int>v[N];

inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

inline int lca(int a,int b)//求两个节点的lca.
{
    //这个应该可以乱写,确信.首先跳到同深度.
    if(dep[b]>dep[a])    swap(a,b);
    //把大的放前面,跳小的.ww
    for(int i=18;i>=0;i--)
    {
        if(dep[f[a][i]]>=dep[b])    a=f[a][i];
    }if(a==b)    return a;
    for(int i=18;i>=0;i--)
    {
        if(f[a][i]!=f[b][i])
        {
            a=f[a][i];
            b=f[b][i];
        }
    }return f[a][0];
}

inline int dis(int a,int b)
{
    return dep[a]+dep[b]-2*dep[lca(a,b)];
}//求两个点的树上距离.

void dfs(int u,int fa,int D)
{
    dep[u]=D;f[u][0]=fa;
    for(int i=1;i<M;i++)
    {
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=0;i<(int)v[u].size();i++)
    {
        int x=v[u][i];
        if(x!=fa)    dfs(x,u,D+1);
    }
}//处理原树的深度.

int siz[N],dp[N],root,vis[N];//每个点的子树大小和某个点子树中最大的子树最小是多少.
void f_root(int u,int fa,int tot)
{
    siz[u]=1;dp[u]=0;
    for(int i=0;i<(int)v[u].size();i++)
    {
        int x=v[u][i];
        if(x==fa||vis[x])    continue;
        f_root(x,u,tot);siz[u]+=siz[x];
        dp[u]=max(dp[u],siz[x]);
    }dp[u]=max(dp[u],tot-siz[u]);
    if(dp[u]<dp[root])    root=u;
}

int dfa[N],dsiz[N];//记录当前u节点在虚树上的父亲节点是哪个.重心包含的虚数大小.
void rebuild(int u,int tot)
{
    vis[u]=1;dsiz[u]=tot;
    for(int i=0;i<(int)v[u].size();i++)
    {
        int x=v[u][i];
        if(vis[x])    continue;
        int Tot=siz[x]<siz[u]?siz[x]:(tot-siz[u]);
        dp[root=0]=2e9;
        f_root(x,u,Tot);dfa[root]=u;
        rebuild(root,Tot);
    }
}//建立虚树.
int rt1[N],rt2[N];
struct xds{
    int lc[N<<3],rc[N<<3],sum[N<<3],size;//存这个节点的左儿子,右儿子,以及区间的和,然后就是推动的下标.
    void update(int &u,int pos,int k,int l,int r)
    {
        if(!u)    u=++size;
        sum[u]+=k;
        if(l==r)    return;
        int mid=(l+r)>>1;
        if(pos<=mid)    update(lc[u],pos,k,l,mid);
        else            update(rc[u],pos,k,mid+1,r);
    }
    int query(int u,int L,int R,int l,int r)//在[l,r]查询[L,R].
    {
        if(L<=l&&r<=R)    return sum[u];
        else if(L>r||R<l||!u)    return 0;
        int mid=(l+r)>>1;
        return query(lc[u],L,R,l,mid)+query(rc[u],L,R,mid+1,r);
    }
    void clear() {memset(lc,0,sizeof(lc));memset(rc,0,sizeof(rc));memset(sum,0,sizeof(sum));size=0;}
}t1,t2;//用于单点修改,区间查询.

void update(int u,int Val)
{
    int now=u;
    while(now)
    {
        int fa=dfa[now];
        t1.update(rt1[now],dis(now,u),Val,0,dsiz[now]);
if(fa)    t2.update(rt2[now],dis(fa,u),Val,0,dsiz[fa]);
        now=fa;
    }
}

inline int query(int u,int k)
{
    int res=0;
    int now=u,last=0;
    while(now)
    {
        int d=dis(u,now);
        if(d>k)    {last=now;now=dfa[now];continue;}
        res+=t1.query(rt1[now],0,k-d,0,dsiz[now]);
        if(last)
        {
            res-=t2.query(rt2[last],0,k-d,0,dsiz[now]);
        }
        last=now;now=dfa[now];
    }return res;
}

int main()
{
    int n,q;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        t1.clear();t2.clear();
        for(int i=1;i<=n;i++)
        {
            val[i]=read();
        }
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<M;j++)
            {
                f[i][j]=0;
            }
        }root=0;
        for(int i=0;i<=n;i++)
        {
            vector<int>().swap(v[i]);
            dep[i]=vis[i]=rt1[i]=rt2[i]=0;
            dfa[i]=dsiz[i]=0;
        }
        for(int i=1;i<n;i++)
        {
            int x,y;
            x=read();y=read();
            v[x].push_back(y);
            v[y].push_back(x);
        }dfs(1,0,1);dp[0]=2e9;
        f_root(1,0,n);
        rebuild(root,n);
        for(int i=1;i<=n;i++)
        {
            update(i,val[i]);
        }
        while(q--)
        {
            char op[2];int u,s;
            scanf("%s",op);
            u=read();s=read();
            if(op[0]=='?')
            {
                printf("%d\n",query(u,s));
            }
            else
            {
                update(u,s-val[u]);val[u]=s;
            }
        }
    }
    return 0;
}

这个代码多交几次就好了...
但是lca可以更加快一点...

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+3e4,M=19;
int val[N],dep[N],f[N][M];
vector<int>v[N];

namespace IO {
    template<typename T> void sc(T &x) { //输入
        int f = 1; x = 0;
        char ch = getchar();

        while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
        if(ch == '-') f = -f;
        else x = ch ^ 48;

        while((ch = getchar()) >= '0' && ch <= '9')
            x = (x << 1) + (x << 3) + (ch ^ 48);

        x *= f;
    }

    template<typename T> void _print(T x) {
        if(x > 9) _print(x / 10);
        putchar((x % 10) ^ 48);
    }

   template<typename T>  void pr(T x) {
        if(x < 0) {
            x = -x;
            putchar('-');
        }
        _print(x);
    }
}
using namespace IO;
int Log[N];
int lca(int a,int b)
{
    if(dep[a] < dep[b]) swap(a,b);int k = dep[a] - dep[b];
    for(int i = Log[k];~i;i--) if((k >> i) & 1) a = f[a][i];
    if(a == b) return a;
    for(int i = Log[dep[a]];~i;i--) if(f[a][i] ^ f[b][i])
    a = f[a][i],b = f[b][i];return f[a][0];
}
inline int dis(int a,int b)
{
    return dep[a]+dep[b]-2*dep[lca(a,b)];
}//求两个点的树上距离.

void dfs(int u,int fa,int D)
{
    dep[u]=D;f[u][0]=fa;
    for(int i=1;i<M;i++)
    {
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=0;i<(int)v[u].size();i++)
    {
        int x=v[u][i];
        if(x!=fa)    dfs(x,u,D+1);
    }
}//处理原树的深度.

int siz[N],dp[N],root,vis[N];//每个点的子树大小和某个点子树中最大的子树最小是多少.
void f_root(int u,int fa,int tot)
{
    siz[u]=1;dp[u]=0;
    for(int i=0;i<(int)v[u].size();i++)
    {
        int x=v[u][i];
        if(x==fa||vis[x])    continue;
        f_root(x,u,tot);siz[u]+=siz[x];
        dp[u]=max(dp[u],siz[x]);
    }dp[u]=max(dp[u],tot-siz[u]);
    if(dp[u]<dp[root])    root=u;
}

int dfa[N],dsiz[N];//记录当前u节点在虚树上的父亲节点是哪个.重心包含的虚数大小.
void rebuild(int u,int tot)
{
    vis[u]=1;dsiz[u]=tot;
    for(int i=0;i<(int)v[u].size();i++)
    {
        int x=v[u][i];
        if(vis[x])    continue;
        int Tot=siz[x]<siz[u]?siz[x]:(tot-siz[u]);
        dp[root=0]=2e9;
        f_root(x,u,Tot);dfa[root]=u;
        rebuild(root,Tot);
    }
}//建立虚树.
int rt1[N],rt2[N];
struct xds{
    int lc[N<<3],rc[N<<3],sum[N<<3],size;//存这个节点的左儿子,右儿子,以及区间的和,然后就是推动的下标.
    void update(int &u,int pos,int k,int l,int r)
    {
        if(!u)    u=++size;
        sum[u]+=k;
        if(l==r)    return;
        int mid=(l+r)>>1;
        if(pos<=mid)    update(lc[u],pos,k,l,mid);
        else            update(rc[u],pos,k,mid+1,r);
    }
    int query(int u,int L,int R,int l,int r)//在[l,r]查询[L,R].
    {
        if(L<=l&&r<=R)    return sum[u];
        else if(L>r||R<l||!u)    return 0;
        int mid=(l+r)>>1;
        return query(lc[u],L,R,l,mid)+query(rc[u],L,R,mid+1,r);
    }
    void clear() {memset(lc,0,sizeof(lc));memset(rc,0,sizeof(rc));memset(sum,0,sizeof(sum));size=0;}
}t1,t2;//用于单点修改,区间查询.

void update(int u,int Val)
{
    int now=u;
    while(now)
    {
        int fa=dfa[now];
        t1.update(rt1[now],dis(now,u),Val,0,dsiz[now]);
if(fa)    t2.update(rt2[now],dis(fa,u),Val,0,dsiz[fa]);
        now=fa;
    }
}

inline int query(int u,int k)
{
    int res=0;
    int now=u,last=0;
    while(now)
    {
        int d=dis(u,now);
        if(d>k)    {last=now;now=dfa[now];continue;}
        res+=t1.query(rt1[now],0,k-d,0,dsiz[now]);
        if(last)
        {
            res-=t2.query(rt2[last],0,k-d,0,dsiz[now]);
        }
        last=now;now=dfa[now];
    }return res;
}

int main()
{
    int n,q;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        t1.clear();t2.clear();
        for(int i=1;i<=n;i++)
        {
            sc(val[i]);
        }
        for(int i = 2;i <= n;i++) Log[i] = Log[i >> 1] + 1;
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<M;j++)
            {
                f[i][j]=0;
            }
        }root=0;
        for(int i=0;i<=n;i++)
        {
            vector<int>().swap(v[i]);
            dep[i]=vis[i]=rt1[i]=rt2[i]=0;
            dfa[i]=dsiz[i]=0;
        }
        for(int i=1;i<n;i++)
        {
            int x,y;
            sc(x);sc(y);
            v[x].push_back(y);
            v[y].push_back(x);
        }dfs(1,0,1);dp[0]=2e9;
        f_root(1,0,n);
        rebuild(root,n);
        for(int i=1;i<=n;i++)
        {
            update(i,val[i]);
        }
        while(q--)
        {
            char op[2];int u,s;
            scanf("%s",op);
            sc(u);sc(s);
            if(op[0]=='?')
            {
                pr(query(u,s));
                puts("");
            }
            else
            {
                update(u,s-val[u]);val[u]=s;
            }
        }
    }
    return 0;
}

就不用多交了..