题目（bzoj）
题目（洛谷）
嗯，树剖模板题。
注意查询的技巧：两个点依次往上跳（类似于倍增向上跳，只不过怎么感觉有时比倍增还快？）
就这样，完毕。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#define ll long long
#define llmax LONG_LONG_MAX
#define llmin LONG_LONG_MIN
#define ls id<<1
#define rs id<<1|1
#define inf INT_MAX
#define readf(f) scanf("%lf",&f)
#define N 30005
using namespace std;
template <class _E> inline void read(_E &e)
{
e=0;bool ck=0;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
if(ck)e=-e;
}
int n,Q;
struct edge{int vk;int nxt;}e[N*2];
struct Segment_tree{int l;int r;int mx;int sum;}t[N<<2];
int tt,head[N];
inline void ad(int u,int v)
{
e[++tt].vk=v;
e[tt].nxt=head[u];
head[u]=tt;
}
int a[N];
char c[15];
int siz[N],f[N],top[N],son[N],rank[N],pre[N],dep[N],idx;
void dfs1(int u,int fa)
{
siz[u]=1;
f[u]=fa;
for (int i=head[u];i;i=e[i].nxt)
{
int v=e[i].vk;
if (v==fa) continue;
dep[v]=dep[u]+1;
dfs1(v,u);
siz[u]+=siz[v];
if (!son[u] || siz[v]>siz[son[u]])
son[u]=v;
}
}
void dfs2(int u,int fa)
{
top[u]=fa;rank[u]=++idx;
pre[rank[u]]=u;
if (!son[u]) return;
dfs2(son[u],fa);
for (int i=head[u];i;i=e[i].nxt)
{
int v=e[i].vk;
if (v==son[u] || v==f[u]) continue;
dfs2(v,v);
}
}
inline void up(int id)
{
t[id].mx=max(t[ls].mx,t[rs].mx);
t[id].sum=t[ls].sum+t[rs].sum;
}
void build(int l,int r,int id)
{
t[id].l=l,t[id].r=r;
if (l==r)
{
t[id].mx=t[id].sum=a[pre[l]];
return;
}
int mid=(l+r)>>1;
build(l,mid,ls),build(mid+1,r,rs);
up(id);
}
void update(int pos,int val,int id)
{
int l=t[id].l,r=t[id].r;
if (l==pos && r==pos)
{
t[id].sum=val;
t[id].mx=val;
return;
}
int mid=(l+r)>>1;
if (pos<=mid) update(pos,val,ls);
else update(pos,val,rs);
up(id);
}
int qsum(int l,int r,int id)
{
int L=t[id].l,R=t[id].r;
if (L==l && R==r){return t[id].sum;}
int mid=(L+R)>>1;
if (r<=mid) return qsum(l,r,ls);
else if (l>mid) return qsum(l,r,rs);
else return qsum(l,mid,ls)+qsum(mid+1,r,rs);
}
int qmax(int l,int r,int id)
{
int L=t[id].l,R=t[id].r;
if (L==l && R==r){return t[id].mx;}
int mid=(L+R)>>1;
if (r<=mid) return qmax(l,r,ls);
else if (l>mid) return qmax(l,r,rs);
else return max(qmax(l,mid,ls),qmax(mid+1,r,rs));
}
inline int QMAX(int x,int y)
{
int f1=top[x],f2=top[y],ret=-inf;
while (f1!=f2)
{
if (dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
ret=max(ret,qmax(rank[f1],rank[x],1));
x=f[f1];f1=top[x];
}
if (dep[x]>dep[y]) swap(x,y);
ret=max(ret,qmax(rank[x],rank[y],1));
return ret;
}
inline int QSUM(int x,int y)
{
int f1=top[x],f2=top[y],ret=0;
while (f1!=f2)
{
if (dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
ret+=qsum(rank[f1],rank[x],1);
x=f[f1];f1=top[x];
}
if (dep[x]>dep[y]) swap(x,y);
ret+=qsum(rank[x],rank[y],1);
return ret;
}
int main()
{
read(n);
for (int i=1;i<n;++i)
{
int x,y;
read(x),read(y);
ad(x,y),ad(y,x);
}
for (int i=1;i<=n;++i) read(a[i]);
dfs1(1,0);dfs2(1,1);
build(1,idx,1);
read(Q);
while (Q--)
{
int x,y;
cin>>c;
if (c[1]=='S')
{
read(x),read(y);
printf("%d\n",QSUM(x,y));
}
else if (c[1]=='M')
{
read(x),read(y);
printf("%d\n",QMAX(x,y));
}
else
{
read(x),read(y);
update(rank[x],y,1);
}
}
return 0;
}
另外这份代码在bzoj上会RE，
只需要把那个cin换成scanf就可以了
Comments NOTHING