。。。。。。
by RagnaLP @ 2017-12-18 13:26:14
天
by RagnaLP @ 2017-12-20 13:38:28
@[lazy_people](/space/show?uid=38041) tql
by esphe @ 2019-04-24 13:35:51
@[Evilball](/space/show?uid=62749) 陈年老帖都长满匍匐菌丝了
by RagnaLP @ 2019-04-30 14:45:54
@[RagnaLP](/user/38041) 远古奇案已被破获，但愿你还在
问题有两个：
1.你link_max中没有将mx设为-inf
错误：
```cpp
ll link_max(ll u,ll v) {
ll mx=0;
```
正确：
```cpp
ll link_max(ll u,ll v) {
ll mx=-inf;
```
2.你单点查询时没有加trid，而且单点查询没必要刻意整个区间查询
错误：
```cpp
if(op=="CHANGE") {
cin>>x>>y;
change(x,x,1,y);
}
```
正确：
```cpp
if(op=="CHANGE") {
cin>>x>>y;
change(trid[x],1,y);
}
```
下面是AC代码，为了方便差错，线段树的码风改成我自己的，懒得改回去了。。。
```cpp
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
const ll MAX=100010;
const ll inf=2e10;
struct Edge {
ll v;
ll next;
} e[MAX<<1];
ll a[MAX]= {0};
ll n,m,r,p;
ll head[MAX],vis[MAX]= {0},trid[MAX]= {0},llr[MAX]= {0};
ll dep[MAX]= {0},fa[MAX],siz[MAX],son[MAX]= {0},top[MAX]= {0};
ll real[MAX]= {0};
ll cnt1=0,cnt2=0;
void add(ll u,ll v) {
e[++cnt1].v=v;
e[cnt1].next=head[u];
head[u]=cnt1;
}
void DFS1(ll u) {
siz[u]=1;
son[u]=0;
for(ll i=head[u]; i!=-1; i=e[i].next) {
ll v=e[i].v;
if(v!=fa[u]) {
dep[v]=dep[u]+1;
fa[v]=u;
DFS1(v);
siz[u]+=siz[v];
if(!son[u]||siz[v]>siz[son[u]])son[u]=v;
}
}
}
void DFS2(ll u,ll tp) {
trid[u]=++cnt2;
llr[cnt2]=u;
top[u]=tp;
if(!son[u])return;
DFS2(son[u],tp);
for(ll i=head[u]; i!=-1; i=e[i].next) {
ll v=e[i].v;
if(v!=son[u]&&v!=fa[u])DFS2(v,v);
}
}
struct Node {
ll l,r;
ll val,mx;
Node() {
val=mx=0;
}
}tr[MAX<<2];
void pushup(ll i) {
tr[i].val=tr[i<<1].val+tr[i<<1|1].val;
tr[i].mx=max(tr[i<<1].mx,tr[i<<1|1].mx);
}
void build(ll l,ll r,ll i) {
tr[i].l=l,tr[i].r=r;
if(l==r) {
tr[i].val=tr[i].mx=a[llr[l]];
return;
}
ll mid=(l+r)>>1;
build(l,mid,i<<1);
build(mid+1,r,i<<1|1);
pushup(i);
}
ll query_sum(ll l,ll r,ll i) {
if(tr[i].r<=r&&l<=tr[i].l)return tr[i].val;
ll mid=(tr[i].l+tr[i].r)>>1;
ll ans=0;
if(l<=mid)ans+=query_sum(l,r,i<<1);
if(r>mid)ans+=query_sum(l,r,i<<1|1);
return ans;
}
ll query_max(ll l,ll r,ll i) {
if(tr[i].r<=r&&l<=tr[i].l)return tr[i].mx;
ll mid=(tr[i].l+tr[i].r)>>1;
ll ans=-inf;
if(l<=mid)ans=max(ans,query_max(l,r,i<<1));
if(r>mid)ans=max(ans,query_max(l,r,i<<1|1));
return ans;
}
void change(ll p,ll i,ll k){
if(tr[i].l==tr[i].r){
tr[i].mx=k;
tr[i].val=k;
return;
}
ll mid=(tr[i].l+tr[i].r)>>1;
if(p<=mid)change(p,i<<1,k);
else change(p,i<<1|1,k);
pushup(i);
}
ll link_sum(ll u,ll v) {
ll sum=0;
while(top[u]!=top[v]) {
if(dep[top[v]]>dep[top[u]])swap(u,v);
sum+=query_sum(trid[top[u]],trid[u],1);
u=fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
sum+=query_sum(trid[u],trid[v],1);
return sum;
}
ll link_max(ll u,ll v) {
ll mx=-inf;
while(top[u]!=top[v]) {
if(dep[top[v]]>dep[top[u]])swap(u,v);
mx=max(query_max(trid[top[u]],trid[u],1),mx);
u=fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
mx=max(query_max(trid[u],trid[v],1),mx);
return mx;
}
void Init() {
memset(head,-1,sizeof(head));
cin>>n;
ll u,v;
for(ll i=0; i<n-1; i++) {
cin>>u>>v;
add(u,v);
add(v,u);
}
for(ll i=1; i<=n; i++)cin>>a[i];
}
void solve() {
DFS1(1);
DFS2(1,1);
build(1,cnt2,1);
cin>>m;
ll x,y;
string op;
while(m--) {
cin>>op;
if(op=="CHANGE") {
cin>>x>>y;
change(trid[x],1,y);
}
else if(op=="QMAX") {
cin>>x>>y;
printf("%lld\n",link_max(x,y));
}
else if(op=="QSUM") {
cin>>x>>y;
printf("%lld\n",link_sum(x,y));
}
}
}
int main() {
Init();
solve();
return 0;
}
```
by Lifeㅤgoesㅤon @ 2020-08-15 01:37:09