Rt,此代码实在查不出错,大佬可不可以帮忙查个错,或者给个建议也可以。
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int n,q,_sum,_max,w[30005],nmax[120005],nsum[120005],f[30005],son[30005],d[30005],top[30005],size[30005],rk[30005],id[30005];
vector <int> v[30005];
void Query(int t,int l,int r,int ll,int rr) {
int mid=(l+r)/2;
if(l>=ll&&r<=rr) {
_sum+=nsum[t];
_max=max(_max,nmax[t]);
return ;
}
if(ll<=mid) Query(2*t,l,mid,ll,rr);
if(rr>=mid+1) Query(2*t+1,mid+1,r,ll,rr);
}
void Change(int t,int l,int r,int u,int poi) {
int mid=(l+r)/2;
if(l==r&&l==u) {
nmax[t]=poi;
nsum[t]=poi;
return ;
}
if(rk[u]<=mid) Change(2*t,l,mid,u,poi);
else Change(2*t+1,mid+1,r,u,poi);
nmax[t]=max(nmax[2*t],nmax[2*t+1]);
nsum[t]=nsum[2*t]+nsum[2*t+1];
}
void dfs1(int s,int fa) {
size[s]=1;
f[s]=fa;
d[s]=d[fa]+1;
for(unsigned int i=0;i<v[s].size();i++) {
if(v[s][i]!=fa) {
dfs1(v[s][i],s);
size[s]+=size[v[s][i]];
if(size[v[s][i]]>size[son[s]]) {
son[s]=v[s][i];
}
}
}
}
void dfs2(int s,int fa) {
if(son[s]) {
top[son[s]]=top[fa];
rk[son[s]]=++rk[0];
id[rk[0]]=son[s];
dfs2(son[s],s);
}
for(unsigned int i=0;i<v[s].size();i++) {
if(!top[v[s][i]]) {
top[v[s][i]]=v[s][i];
rk[v[s][i]]=++rk[0];
id[rk[0]]=v[s][i];
dfs2(v[s][i],s);
}
}
}
void Build(int t,int l,int r) {
int mid=(l+r)/2;
if(l==r) {
nmax[t]=w[id[t]];
nsum[t]=w[id[t]];
return ;
}
Build(2*t,l,mid);
Build(2*t+1,mid+1,r);
nmax[t]=max(nmax[2*t],nmax[2*t+1]);
nsum[t]=nsum[2*t]+nsum[2*t+1];
}
void ask(int x,int y) {
int fx=top[x],fy=top[y];
while(fx!=fy) {
if(d[fx]<d[fy]) {
swap(fx,fy);
swap(x,y);
}
Query(1,1,n,x,y);
x=f[fx];
fx=top[x];
}
}
int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<n;i++) {
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++) cin>>w[i];
id[0]=id[1]=top[1]=rk[1]=1;
dfs1(1,0);
dfs2(1,0);
cin>>q;
for(int i=1;i<=q;i++) {
string team;
cin>>team;
if(team=="CHANGE") {
int u,t;
cin>>u>>t;
Change(1,1,n,u,t);
}
if(team=="QMAX") {
int u,v;
cin>>u>>v;
Query(1,1,n,u,v);
cout<<_max<<'\n';
}
if(team=="QSUM") {
int u,v;
cin>>u>>v;
Query(1,1,n,u,v);
cout<<_sum<<'\n';
}
_sum=_max=0;
}
return 0;
}