http://www.lydsy.com/JudgeOnline/problem.php?id=1036 (题目链接)
题意
动态维护树上两点间最大权值和权值和。
Solution
裸树链剖分。
这一篇题解并不是本博客的重点。我在找本题的数据生成器的时候发现了一篇神奇的博客。关于如何制造出一棵树的数据，随机构造prufer。
UPD:当年的自己真是脑残，竟然不会构造树的数据→_→
data
#include<cstdio>
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a[30000+20];
struct nod
{
int id,d;
}d[30000+20];
bool cmpid(nod x,nod y)//按编号排序
{
return x.id<y.id;
}
bool cmp(nod x,nod y)//按度数排序
{
if(x.d!=y.d)return x.d<y.d;
else return x.id<y.id;
}
int main()
{
freopen("1.in","w",stdout);
srand(time(NULL));
int n=rand()%10+1;
cout<<n<<endl;
for(int i=1;i<=n;i++)
{
d[i].d=1;
d[i].id=i;
}
for(int i=1;i<=n-2;i++)a[i]=rand()%n+1;//生成purfer编码
for(int i=1;i<=n-2;i++)d[a[i]].d++;//累加度数
for(int i=1;i<=n-2;i++)
{
sort(d+1,d+n+1,cmp);
int j;
for(j=1;j<=n;j++)if(d[j].d)break;
printf("%d %d
",d[j].id,a[i]);
d[j].d--;
sort(d+1,d+n+1,cmpid);
d[a[i]].d--;
} //模拟上述过程，找度数为1且编号最小的和purfer编码中当前位
sort(d+1,d+n+1,cmp);
printf("%d %d
",d[n-1].id,d[n].id);//最后两个点之间连边
for(int i=1;i<=n;i++)
{
printf("%d ",(rand()%20)-10);
}
int m=rand()%20+1;
cout<<endl;
cout<<m<<endl;
for(int i=1;i<=m;i++)
{
int s=rand()%3+1;
if(s==1)printf("QMAX ");
if(s==2)printf("QSUM ");
if(s==3)printf("CHANGE ");
int a=rand()%n+1;
int b=rand()%a+1;
while(a==b)
{
a=rand()%n+1;
b=rand()%a+1;
}
cout<<a<<" "<<b<<endl;
}
return 0;
}
代码
// bzoj1036
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
#define inf 2147483640
#define LL long long
#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std;
inline LL getint() {
LL x=0,f=1;char ch=getchar();
while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=30010;
struct edge {int to,next;}e[maxn<<2];
struct tree {int s,mx,l,r;}tr[maxn<<2];
int a[maxn],pos[maxn],head[maxn],bl[maxn],size[maxn],deep[maxn],fa[maxn][20],bin[20];
int cnt,n,q;
void insert(int u,int v) {
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
void build(int k,int s,int t) {
tr[k].l=s,tr[k].r=t,tr[k].s=0,tr[k].mx=-inf;
if (s==t) return;
int mid=(s+t)>>1;
build(k<<1,s,mid);
build(k<<1|1,mid+1,t);
}
void update(int k,int s,int val) {
int l=tr[k].l,r=tr[k].r;
if (l==r && l==s) {tr[k].s=tr[k].mx=val;return;}
int mid=(l+r)>>1;
if (s<=mid) update(k<<1,s,val);
else update(k<<1|1,s,val);
tr[k].s=tr[k<<1].s+tr[k<<1|1].s;
tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);
}
int querymx(int k,int s,int t) {
int l=tr[k].l,r=tr[k].r;
if (l==s && r==t) return tr[k].mx;
int mid=(l+r)>>1;
if (t<=mid) return querymx(k<<1,s,t);
else if (s>mid) return querymx(k<<1|1,s,t);
else return max(querymx(k<<1,s,mid),querymx(k<<1|1,mid+1,t));
}
int querys(int k,int s,int t) {
int l=tr[k].l,r=tr[k].r;
if (l==s && r==t) return tr[k].s;
int mid=(l+r)>>1;
if (t<=mid) return querys(k<<1,s,t);
else if (s>mid) return querys(k<<1|1,s,t);
else return querys(k<<1,s,mid)+querys(k<<1|1,mid+1,t);
}
void dfs1(int x) {
size[x]=1;
for (int i=1;i<20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa[x][0]) {
deep[e[i].to]=deep[x]+1;
fa[e[i].to][0]=x;
dfs1(e[i].to);
size[x]+=size[e[i].to];
}
}
void dfs2(int x,int chain) {
bl[x]=chain;
pos[x]=++cnt;
update(1,pos[x],a[x]);
int k=0;
for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa[x][0])
if (size[k]<size[e[i].to]) k=e[i].to;
if (k!=0) dfs2(k,chain);
for (int i=head[x];i;i=e[i].next)
if (e[i].to!=fa[x][0] && e[i].to!=k) dfs2(e[i].to,e[i].to);
}
int lca(int x,int y) {
if (deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for (int i=0;bin[i]<=t;i++) if (bin[i]&t) x=fa[x][i];
for (int i=19;i>=0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return x==y?x:fa[x][0];
}
int solvemx(int x,int f) {
if (x==f) return a[x];
int mx=-inf;
while (bl[x]!=bl[f]) {
mx=max(mx,querymx(1,pos[bl[x]],pos[x]));
x=fa[bl[x]][0];
}
if (pos[f]<=pos[x]) mx=max(mx,querymx(1,pos[f],pos[x]));
return mx;
}
int solves(int x,int f) {
if (x==f) return a[x];
int s=0;
while (bl[x]!=bl[f]) {
s+=querys(1,pos[bl[x]],pos[x]);
x=fa[bl[x]][0];
}
if (pos[f]<=pos[x]) s+=querys(1,pos[f],pos[x]);
return s;
}
int main() {
bin[0]=1;for (int i=1;i<20;i++) bin[i]=bin[i-1]<<1;
scanf("%d",&n);
for (int i=1;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
insert(u,v);
}
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
cnt=0;
build(1,1,n);
dfs1(1);dfs2(1,1);
scanf("%d",&q);
while (q--) {
char ch[10];int x,y;
scanf("%s%d%d",ch,&x,&y);
if (ch[0]=='C') update(1,pos[x],y),a[x]=y;
else if (ch[1]=='M') {
int f=lca(x,y);
printf("%d
",max(solvemx(x,f),solvemx(y,f)));
}
else {
int f=lca(x,y);
printf("%d
",solves(x,f)+solves(y,f)-a[f]);
}
}
return 0;
}