1.ZJOI树的统计
板子题 因为初始化没打改了几个小时 改到双腿软着出的机房（身体素质感人
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 300000
#define ls x<<1
#define rs x<<1|1
using namespace std;
,v[maxn],top[maxn],son[maxn],fa[maxn],de[maxn],w[maxn],z,tree1[maxn],tree2[maxn],sz[maxn];
];
struct eg
{
int to;
int nxt;
}b[maxn];
void link(int x,int y)
{
b[++tot].nxt=head[x];
b[tot].to=y;
head[x]=tot;
}
void dfs1(int x,int f)
{
sz[x]=,fa[x]=f;
;i=b[i].nxt)
{
int t=b[i].to;
if (t==f) continue;
de[t]=de[x]+;
dfs1(t,x);
sz[x]+=sz[t];
||sz[son[x]]<sz[t]) son[x]=t;
}
}
void dfs2(int x,int tp)
{
top[x]=tp,w[x]=++z；
) dfs2(son[x],tp);
else return ;
;i=b[i].nxt)
{
int t=b[i].to;
if (t!=fa[x]&&t!=son[x]) dfs2(t,t);
}
}
void build(int x,int l,int r)
{
tree2[x]=,tree1[x]=-;
if (l==r) return ;
;
build (ls,l,mid);
build (rs,mid+,r);
}
void updata(int x,int l,int r,int d,int y)
{
if (l==r&&l==d)
{
tree1[x]=y;
tree2[x]=y;
return ;
}
;
if (d<=mid)updata(ls,l,mid,d,y);
,r,d,y);
tree1[x]=max(tree1[ls],tree1[rs]);
tree2[x]=tree2[ls]+tree2[rs];
}
int qsum(int x,int l,int r,int ll,int rr)
{
if (ll==l&&r==rr) return tree2[x];
;
,r,ll,rr);
else if (rr<=mid) return qsum(ls,l,mid,ll,rr);
,r,mid+,rr);
}
int qmax(int x,int l,int r,int ll,int rr)
{
if (ll==l&&r==rr) return tree1[x];
;
if (rr<=mid) return qmax(ls,l,mid,ll,rr);
,r,ll,rr);
,r,mid+,rr));
}
int find(int x,int y,int flag)
{
)
{
;
int f1=top[x],f2=top[y];
while(f1!=f2)
{
if(de[f1]<de[f2]) swap(f1,f2),swap(x,y);
ans=max(ans,qmax(,,z,w[f1],w[x]));
x=fa[f1],f1=top[x];
}
if (de[x]>de[y]) swap(x,y);
,,z,w[x],w[y]));
}
)
{
;
int f1=top[x],f2=top[y];
while (f1!=f2)
{
if(de[f1]<de[f2]) swap(f1,f2),swap(x,y);
ans+=qsum(,,z,w[f1],w[x]);
x=fa[f1],f1=top[x];
}
if (de[x]>de[y]) swap(x,y);
,,z,w[x],w[y]);
}
}
int main()
{
memset(head, -, sizeof(head));
memset(son, -, sizeof(son));
scanf ("%d",&n);
;i<n;++i)
{
int x,y;
scanf ("%d%d",&x,&y);
link(x,y);
link(y,x);
}
;i<=n;++i)
scanf ("%d",&v[i]);
de[]=;
dfs1(,);
dfs2(,);
build(,,z);
;i<=n;++i) updata(,,z,w[i],v[i]);
int q;
scanf("%d",&q);
;i<=q;++i)
{
scanf ("%s",s);
int x,y;
scanf ("%d%d",&x,&y);
]=='C')
updata(,,z,w[x],y);
]=='M')
printf());
]=='S')
printf());
}
;
}
2.HAOI树上操作
这一次是被数组大小给困住了 好不容易反应过来开大了tree的大小结果我没有开大lazy的？？（黑人问号
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 100002
#define LL long long
#define ls x<<1
#define rs x<<1|1
using namespace std;
,df=;
*N],to[*N],nxt[*N],dfn[N];
int sz[N],tp[N],son[N],de[N],fa[N],ed[N];
LL tree[*N],v[N],lazy[*N];
void link(int x,int y)
{
nxt[++tot]=head[x];
to[tot]=y;
head[x]=tot;
}
void dfs(int x)
{
sz[x]=;
for (int i=head[x];i;i=nxt[i])
{
int t=to[i];
if (t==fa[x]) continue;
de[t]=de[x]+;
fa[t]=x;
dfs(t);
sz[x]+=sz[t];
if (sz[t]>sz[son[x]]) son[x]=t;
}
}
void dfs1(int x,int top)
{
dfn[x]=++df,tp[x]=top;
if (son[x]) dfs1(son[x],top);
for (int i=head[x];i;i=nxt[i])
{
int t=to[i];
if (t==fa[x]||t==son[x]) continue;
dfs1(t,t);
}
ed[x]=df;
}
void down (int x,int l,int r)
{
;
tree[ls]+=lazy[x]*(mid-l+);
tree[rs]+=lazy[x]*(r-mid);
lazy[ls]+=lazy[x];
lazy[rs]+=lazy[x];
lazy[x]=;
}
void update(int x,int l,int r,int ll,int rr,LL w)
{
if (l!=r) down(x,l,r);
if (ll<=l&&r<=rr)
{
tree[x]+=w*(r-l+);
lazy[x]=w;
return ;
}
;
if (ll<=mid) update(ls,l,mid,ll,rr,w);
,r,ll,rr,w);
tree[x]=tree[ls]+tree[rs];
}
LL query(int x,int l,int r,int ll,int rr)
{
if (l!=r) down(x,l,r);
if (ll<=l&&r<=rr) return tree[x];
;
LL ans=;
if (ll<=mid) ans+=query(ls,l,mid,ll,rr);
,r,ll,rr);
return ans;
}
LL lca(int x)
{
LL ans=;
)
{
ans+=query(,,n,dfn[tp[x]],dfn[x]);
x=fa[tp[x]];
}
ans+=query(,,n,,dfn[x]);
return ans;
}
int main()
{
scanf ("%d%d",&n,&m);
;i<=n;++i) scanf ("%lld",&v[i]);
;i<n;++i)
{
int x,y;
scanf ("%d%d",&x,&y);
link(x,y);
link(y,x);
}
de[]=;
dfs(),dfs1(,);
;i<=n;++i) update(,,n,dfn[i],dfn[i],v[i]);
;i<=m;++i)
{
//cout<<query(1,1,n,dfn[2],dfn[2])<<"**"<<endl;
;
scanf ("%d",&fl);
)
{
int x,a;
scanf ("%d%d",&x,&a);
update(,,n,dfn[x],dfn[x],a);
}
)
{
int x,a;
scanf ("%d%d",&x,&a);
update(,,n,dfn[x],ed[x],a);
}
)
{
int x;
scanf ("%d",&x);
printf("%lld\n",lca(x));
}
}
;
}
最后再带上第一次在考试中（又是基本没学的状态下考的）遇到的树剖题
qtree系列中的一道
然而这个是强行lca做的 效果好像还可以啊
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 50000
using namespace std;
,he[maxn],nxt[maxn],to[maxn],di[maxn],de[maxn],dis[maxn];
bool vis[maxn];
];
];
void link(int x,int y,int dis)
{
nxt[++tot]=he[x];
to[tot]=y;
di[tot]=dis;
he[x]=tot;
}
void dfs(int u)
{
vis[u]=;
for (int i=he[u];i;i=nxt[i])
{
int t=to[i];
if (vis[t]) continue;
f[t][]=u;
de[t]=de[u]+;
dis[t]=di[i];
dfs(t);
}
}
void ff()
{
;i<=));++i)
;j<=n;++j)
f[j][i]=f[f[j][i-]][i-];
}
int lca(int x,int y)
{
;
if (de[x]<de[y]) swap(x,y);
int q=de[x]-de[y];
,yy;
;(<<i)<=n;++i)
<<i)) x=f[x][i];
])
ans=max(ans,dis[i]);
//cout<<ans<<"&&"<<endl;
if (x==y) return ans;
xx=x,yy=y;
));i>=;i--)
{
if (f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
}
//cout<<x<<" "<<y<<"**"<<endl;
];i=f[i][])
ans=max(ans,dis[i]);
];i=f[i][])
ans=max(ans,dis[i]);
return ans;
}
int main()
{
scanf ("%d",&n);
;i<n;++i)
{
int x,y,r;
scanf ("%d%d%d",&x,&y,&r);
link(x,y,r);
link(y,x,r);
}
de[]=;
dfs();
ff();
)
{
scanf ("%s",s);
]=='D') break;
]=='C')
{
int x,y;
scanf("%d%d",&x,&y);
*x],yy=to[*x-];
//cout<<xx<<" "<<yy<<"&&"<<endl;
]==yy) dis[xx]=y;
]==xx) dis[yy]=y;
}
]=='Q')
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
}
;
}