题意

给 个点 条边的无向图，点 有种类 与权值 ，边有边权有两种操作：

1. 将某个点的权值增加。
2. 询问从 出发走边权小于 的边形成的连通块中，每种种类的最大权值的和是多少。

每种种类不超过十个点。

思路

因为有走过的最大边不能超过一个数这样的条件，我们马上就可以想到 Kruskal 重构树。

这样我们的连通块就变成了重构树上的一颗子树了。

我们思考“每种种类不超过十个点”这个诡异限制有什么用，首先可以猜测这个 是直接乘进最终复杂度里的。

然后我们思考两个同种类的点 之间会有什么互动，比如设 的权值较小。那么从 向上走时，这一段的这个种类的最大点为 ，直到我们走到的这个点的子树中包含了 为止。然后再向上走最大点就变成了 ，直到包含一个比 权值更大的同类点。

而显然的，如果我们走了一段最大值为 的权值的点，那么从 到这一段点的最大点一定全为 。

那么我们不妨设每个（原图中的）点有一个“控制范围”，表示从这个点向上走直到一个点包含了比这个点权值更大的相同种类的点。

在一个点的控制范围内，这个种类的最大值为这个点的权值。

显然的，如果我们正确地维护了每个点的控制区间，那么查询只需要向上倍增到最上的一个点，然后将这个点属于的所有控制区间所代表的权值加起来就可以得到答案了。

接下来我们考虑修改操作，权值只增不减，这是个很好的性质，这意味着只有可能是这个被增加的点获得更大的控制区间，而不可能是将控制区间让给某个点。

似乎减小也是可以做的，但是这样就要分讨，而且不好写，会把题出的很不优雅。

但是出题人整多组数据要各种清空其实就挺不优雅的。

勉强当 ACM 特性看待。

所以我们可以从这个点一路向上，对于新获得的控制区间，我们将新的权值与原权值做差就可以变成一个只加的操作。于是对一个维护出子树的答案就十分简单了。

接下来考虑优化复杂度，我们发现从一个点向上（对于同一个种类的点）最多只有十个不同的控制区间（同一种类的点的 LCA 最多只有十个，而这些 LCA 之间的控制区间是不会改变的）。所以我们在向上拓展时，可以对于最近的同种类的点来进行判断，跳到相应的 LCA 然后进行树上路径修改。

由于我比较无脑，树上路径修改写了树剖。

CODE

调试惊险又刺激，在距离结束还有 1min46s 时获得了 AC。

不是很懂都 2022 年了怎么还有 OJ 没有开全栈的，导致我没敢写 DFS。

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=400010,ON=200010,FSIZE=1<<26;
using uni=unsigned;
using ll=long long;
using db=double;
using iter=vector<int>::iterator;
int n,m,q;
int s[N],c[N],in[N],st[N],sze,cnt;
int lcas[ON][10][10],pl[N];
int mx[N],up[N][21];
int dfn[N],dfsn,hs[N],sz[N],tp[N];
ll p[N];
bool geths[N];
struct edge{int u,v,l;}e[N];
vector<int> t[N];
vector<int> col[N];
struct ST{
    ll a[N<<2];
    void clear(){memset(a,0,sizeof(a));}
    void add(int x,int y,int z,int m=1,int l=1,int r=dfsn){
        if(x<=l&&r<=y){
            a[m]+=z;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid) add(x,y,z,m<<1,l,mid);
        if(mid<y) add(x,y,z,m<<1|1,mid+1,r);
    }
    ll operator[](int x){
        ll re=a[1];
        int m=1,l=1,r=dfsn,mid;
        for(;l<r;re+=a[m])
            if(x<=(mid=(l+r)>>1)){
                m<<=1;
                r=mid;
            }else{
                m=m<<1|1;
                l=mid+1;
            }
        return(re);
    }
}St;
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;48>*InF||*InF>57;++InF);
    for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
int root(int x){return(s[x]?s[x]=root(s[x]):x);}
int kruskal(int n,int m){
    sort(e+1,e+m+1,[](edge a,edge b){return(a.l<b.l);});
    cnt=n;
    for(int i=1,x,y;i<=m;++i){
        if((x=root(e[i].u))!=(y=root(e[i].v))){
            p[s[x]=s[y]=++cnt]=e[i].l;
            t[cnt].push_back(x);
            t[cnt].push_back(y);
        }
    }
    return(cnt);
}
iter tpi[N];
void dfs0(int sp){
    for(int i=1;i<=cnt;++i) tpi[i]=(iter)nullptr;
    for(st[sze=1]=sp;sze;){
        int x=st[sze];
        auto &i=tpi[x];
        if(i==(iter)nullptr){
            sz[x]=1;
            for(int &i=mx[x]=1;up[up[x][i-1]][i-1];++i)
                up[x][i]=up[up[x][i-1]][i-1];
            i=t[x].begin();
            if(c[x]){
                auto &tmp=col[c[x]];
                pl[x]=tmp.size();
                for(auto j=tmp.begin();j!=tmp.end();++j){
                    lcas[c[x]][pl[x]][j-tmp.begin()]=
                    lcas[c[x]][j-tmp.begin()][pl[x]]=root(*j);
                }
                tmp.push_back(x);
            }
        }else{
            sz[x]+=sz[*i];
            if(sz[*i]>sz[hs[x]]) hs[x]=*i;
            ++i;
        }
        if(i!=t[x].end()) up[st[++sze]=*i][0]=x;
        else{
            s[x]=up[x][0];
            --sze;
        }
    }
}
void dfs1(int sp){
    for(int i=1;i<=cnt;++i) tpi[i]=(iter)nullptr;
    tp[sp]=sp;
    for(st[sze=1]=sp;sze;){
        int x=st[sze];
        if(!geths[x]){
            dfn[x]=++dfsn;
            geths[x]=1;
            if(hs[x]) tp[st[++sze]=hs[x]]=tp[x];
            continue;
        }
        auto &i=tpi[x];
        if(i==(iter)nullptr) i=t[x].begin();
        else ++i;
        for(;i!=t[x].end()&&*i==hs[x];++i);
        if(i!=t[x].end()) tp[st[++sze]=*i]=*i;
        else --sze;
    }
}
ll get(int x,int y){
    for(int i=mx[x];~i;--i)
        if(p[up[x][i]]<=y&&up[x][i]) x=up[x][i];
    return(St[dfn[x]]);
}
void modify(int t,int x,ll add){
    for(;tp[t]!=tp[x];x=up[tp[x]][0])
        St.add(dfn[tp[x]],dfn[x],add);
    if(t!=x) St.add(dfn[t]+1,dfn[x],add);
}
void add(int x,int y){
    p[x]+=y;
    if(col[c[x]].size()<2){
        modify(0,x,y);
        return;
    }
    ll lmo=y;
    for(int np=pl[x],l=np,r=np,lp=x;1;){
        int lc=l?lcas[c[x]][l-1][np]:0,
            rc=r+1<(int)col[c[x]].size()?lcas[c[x]][np][r+1]:0;
        if(!lc&&!rc){
            modify(0,lp,lmo);
            return;
        }
        if(dfn[lc]>dfn[rc]){
            modify(lc,lp,lmo);
            int lst=p[col[c[x]][l-1]];
            if(lst<p[x]){
                lp=lc;
                lmo=min(p[x]-lst,lmo);
            }else return;
            --l;
        }else{
            modify(rc,lp,lmo);
            int lst=p[col[c[x]][r+1]];
            if(lst<p[x]){
                lp=rc;
                lmo=min(p[x]-lst,lmo);
            }else return;
            ++r;
        }
    }
}
void work(){
    memset(s,0,sizeof(s));
    memset(p,0,sizeof(p));
    memset(c,0,sizeof(c));
    memset(up,0,sizeof(up));
    memset(hs,0,sizeof(hs));
    memset(lcas,0,sizeof(lcas));
    memset(geths,0,sizeof(geths));
    St.clear();
    read(n);read(m);read(q);
    for(int i=1;i<=n+n;++i){
        t[i].clear();
        col[i].clear();
    }
    for(int i=1;i<=n;++i) read(c[i]);
    for(int i=1;i<=n;++i) read(in[i]);
    for(int i=1;i<=m;++i){
        read(e[i].u);read(e[i].v);read(e[i].l);
    }
    kruskal(n,m);
    memset(s,0,sizeof(s));
    dfsn=0;
    dfs0(cnt);
    dfs1(cnt);
    for(int i=1;i<=n;++i) add(i,in[i]);
    for(int i=1,t,x,y;i<=q;++i){
        read(t);read(x);read(y);
        if(t) printf("%lld\n",get(x,y));
        else add(x,y);
    }
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    int t=0;
    for(read(t);t--;work());
    fclose(stdin);
    fclose(stdout);
    return(0);
}