bzoj1036：裸，调了好久，然后1A爽爆。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define adde(u,v) add(u,v) ,add(v,u)
#define qwq(x) for(edge *o=head[x];o;o=o->next)
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
int read(){
int x=0;char c=getchar();bool f=true;
while(!isdigit(c)) {
if(c=='-') f=false;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return f?x:-x;
}
const int nmax=30005;
const int inf=0x7f7f7f7f;
struct edge{
int to;
edge *next;
};
edge edges[nmax<<1],*pt=edges,*head[nmax];
bool vis[nmax];
int id[nmax],idx[nmax<<2],fa[nmax],size[nmax],son[nmax],dep[nmax],tp[nmax],w[nmax],n;
char ch[100];
struct node{
int maxn,sum;
};
node tree[nmax<<2];
void add(int s,int t){
pt->to=t;pt->next=head[s];head[s]=pt++;
}
void dfs(int x){
vis[x]=1;size[x]=1;
qwq(x){
int to=o->to;
if(!vis[to]){
dep[to]=dep[x]+1;fa[to]=x;dfs(to);
size[x]+=size[to];
if(!son[x]||size[to]>size[son[x]]) son[x]=to;
}
}
}
void Dfs(int x,int top){
id[x]=++id[0];idx[id[0]]=x;tp[x]=top;
if(son[x]) Dfs(son[x],top);
qwq(x) if(!id[o->to]) Dfs(o->to,o->to);
}
void pushup(int x){
node &o=tree[x];node &tl=tree[x<<1];node &tr=tree[x<<1|1];
o.maxn=max(tl.maxn,tr.maxn);o.sum=tl.sum+tr.sum;
}
void build(int l,int r,int x){
node &o=tree[x];
if(l==r) {
o.maxn=o.sum=w[idx[l]];return ;
}
int m=(l+r)>>1;build(lson);build(rson);pushup(x);
}
void update(int p,int add,int l,int r,int x){
if(l==r) {
tree[x].maxn=tree[x].sum=add;return ;
}
int m=(l+r)>>1;
p<=m?update(p,add,lson):update(p,add,rson);pushup(x);
}
int querysum(int tl,int tr,int l,int r,int x){
if(tl<=l&&tr>=r) return tree[x].sum;
int m=(l+r)>>1;int ans=0;
if(tl<=m) ans+=querysum(tl,tr,lson);
if(tr>m) ans+=querysum(tl,tr,rson);
return ans;
}
int querymax(int tl,int tr,int l,int r,int x){
if(tl<=l&&tr>=r) return tree[x].maxn;
int m=(l+r)>>1;int ans=-inf;
if(tl<=m) ans=max(ans,querymax(tl,tr,lson));
if(tr>m) ans=max(ans,querymax(tl,tr,rson));
return ans;
}
int qsum(int a,int b){
int ans=0;
while(tp[a]!=tp[b]){
if(dep[tp[a]]>dep[tp[b]]) swap(a,b);
ans+=querysum(id[tp[b]],id[b],1,n,1);
b=fa[tp[b]];
}
if(dep[a]>dep[b]) swap(a,b);
ans+=querysum(id[a],id[b],1,n,1);return ans;
}
int qmax(int a,int b){
int ans=-inf;
while(tp[a]!=tp[b]){
if(dep[tp[a]]>dep[tp[b]]) swap(a,b);
ans=max(ans,querymax(id[tp[b]],id[b],1,n,1));
b=fa[tp[b]];
}
if(dep[a]>dep[b]) swap(a,b);
ans=max(ans,querymax(id[a],id[b],1,n,1));return ans;
}
void test(int l,int r,int x){
if(l==r) printf("%d ",tree[x].maxn);
else{
int m=(l+r)>>1;test(lson);test(rson);
}
}
int main(){
n=read();
rep(i,n-1) {
int s=read(),t=read();adde(s,t);
}
/*rep(i,n){
for(edge *o=head[i];o;o=o->next) printf("%d ",o->to);
printf("
");
}*/
clr(vis,0);clr(son,0);dep[1]=0;
clr(id,0);clr(idx,0);id[0]=0;
dfs(1);Dfs(1,1);
/*rep(i,n){
printf("%d:%d %d %d %d
",i,fa[i],son[i],size[i],dep[i]);
}*/
rep(i,n) w[i]=read();
// rep(i,n) printf("%d ",id[i]);
build(1,n,1);//test(1,n,1);
int m=read();
rep(i,m){
scanf("%s",ch);int a=read(),b=read();
if(ch[0]=='C') update(id[a],b,1,n,1);
else if(ch[1]=='M') printf("%d
",qmax(a,b));
else printf("%d
",qsum(a,b));
}
return 0;
}
hdu3966：挺裸的。然后一直WA。。然后拿标程对拍没错啊。。。最后的方法是要数据了。。。然后并不知道怎么要数据qaq。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define addedge(u,v) adde(u,v),adde(v,u)
#define qwq(x) for(edge *o=head[x];o;o=o->next)
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
int read(){
int x=0;char c=getchar();bool f=true;
while(!isdigit(c)){
if(c=='-') f=false;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return f?x:-x;
}
const int nmax=55555;
const int inf=0x7f7f7f7f;
struct edge{
int to;edge *next;
};
edge edges[nmax<<2],*pt,*head[nmax];
int son[nmax],fa[nmax],dep[nmax],size[nmax],w[nmax];
bool vis[nmax];
int id[nmax],idx[nmax],tp[nmax],col[nmax<<2];
int n,m,p;
void adde(int s,int t){
pt->to=t;pt->next=head[s];head[s]=pt++;
}
void dfs(int x){
size[x]=1;vis[x]=1;
qwq(x){
int to=o->to;
if(!vis[to]){
fa[to]=x;dep[to]=dep[x]+1;dfs(to);size[x]+=size[to];
if(!son[x]||size[son[x]]<size[to]) son[x]=to;
}
}
}
void Dfs(int x,int top){
id[++id[0]]=x;idx[x]=id[0];tp[x]=top;
//Dfs(son[x],top);
if(son[x]) Dfs(son[x],top);
qwq(x) if(!idx[o->to]) Dfs(o->to,o->to);
}
void pushdown(int x){
if(col[x]){
col[x<<1]+=col[x];col[x<<1|1]+=col[x];col[x]=0;return ;
}
}
void update(int tl,int tr,int add,int l,int r,int x){
if(tl<=l&&tr>=r) {
col[x]+=add;return ;
}
pushdown(x);
int m=(l+r)>>1;
if(tl<=m) update(tl,tr,add,lson);
if(tr>m) update(tl,tr,add,rson);
}
void solve(int s,int t,int add){
// if(dep[tp[s]]>dep[tp[t]]) swap(s,t);
while(tp[s]!=tp[t]){
if(dep[tp[s]]>dep[tp[t]]) swap(s,t);
update(idx[tp[t]],idx[t],add,1,n,1);
t=fa[tp[t]];
}
if(dep[s]>dep[t]) swap(s,t);
update(idx[s],idx[t],add,1,n,1);
}
int query(int p,int l,int r,int x){
if(l==r) return col[x]+w[id[l]];
int m=(l+r)>>1;pushdown(x);
if(p<=m) return query(p,lson);else return query(p,rson);
}
int main(){
freopen("data.out","r",stdin);
freopen("my.out","w",stdout);
while(scanf("%d%d%d",&n,&m,&p)==3){
int s,t,add;pt=edges;clr(head,0);
rep(i,n) w[i]=read();
rep(i,m){
s=read(),t=read();addedge(s,t);
}
/*rep(i,n){
qwq(i) printf("%d ",o->to);
printf("
");
}*/
clr(fa,0);clr(vis,0);clr(son,0);dep[1]=0;
id[0]=0;clr(idx,0);
dfs(1);Dfs(1,1);
// rep(i,n) printf("%d:%d %d %d %d
",i,fa[i],size[i],son[i],dep[i]);
// rep(i,n) printf("%d ",idx[i]);
// rep(i,id[0]) printf("%d ",id[i]);
char c;clr(col,0);
rep(i,p){
c=getchar();
if(c=='I') {
s=read(),t=read(),add=read();
solve(s,t,add);
}else if(c=='D'){
s=read(),t=read(),add=read();
solve(s,t,-add);
}else s=read(),printf("%d
",query(idx[s],1,n,1));
// for(int i=1;i<=3;i++) printf("%d ",col[i]);
// printf("%d
",col[1]);
}
}
return 0;
}