板子
ll lg[40];
ll dep[N],fa[N][40];
ll dis[N];
void dfs(ll u,ll f)
{
dep[u]=dep[f]+1;
fa[u][0]=f;
for(int i=1;i<=lg[dep[u]];i++)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=head[u];i;i=next[i])
{
ll v=e[i].v;
if(v==f)continue;
dis[v]=dis[u]+e[i].w;
dfs(v,u);
}
}
ll lca(ll a,ll b)
{
if(dep[a]<dep[b])swap(a,b);
while(dep[a]>dep[b])
{
a=fa[a][lg[dep[a]-dep[b]]];
}
if(a==b)return a;
for(int i=lg[dep[a]];i>=0;i--)
{
if(fa[a][i]!=fa[b][i])
{
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
void lgp()
{
for(int i=2;i<=n;i++)
{
lg[i]=lg[i-1]+((2<<lg[i-1])==i);
}
}
牧场旅行
记一个比较容易的结论：
树上路径长：
[dis(u,v)=dis(1,u)+dis(1,v)-2cdot dis[1,lca(u,v)]
]
这道题就是用这个结论套(lca)板子
然后注意写不要在(if)语句的同行加分号……（就是直接判了个寂寞）
Distance Queries 距离咨询
怕不是和牧场旅行完全重题……
记下是因为要注意预处理(lg)数组的时候是从(1)开始的
然后输入的方向根本没用……
货车运输&&星际导航
这两题就只是最大最小相反好吧……
之前学树剖的时候做过货车这道题，树剖方法见这篇博客
这里记一下倍增方法
首先容易想到这条符合题意的路径肯定是在无向图的最大/最小生成树上的，于是先用(kruskal)把这棵树抠出来，然后树上倍增求即可
相当于一个树上的(RMQ)，所以用倍增解决，跟求(lca)时差不了太多，就是多维护了一个区间最值数组，然后跳的时候顺便记得用它更新答案
再就是(kruskal)之前先把边存在别的地方，要不会出玄学错误……
代码（以货车运输为例）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ZZ_zuozhe int main()
#define N 50005
#define E 500005
ll n,m,a,b,c,q;
struct edge
{
ll u,v,w;
}e[E],t[E];
ll tot=0,head[E],next[E];
void add(ll a,ll b,ll c)
{
++tot;
e[tot].u=a;
e[tot].v=b;
e[tot].w=c;
next[tot]=head[a];
head[a]=tot;
}
bool cmp(edge a,edge b)
{
return a.w>b.w;
}
ll lg[E];
void lgp()
{
for(int i=2;i<=m;i++)lg[i]=lg[i>>1]+1;
}
ll dep[N],fa[N][30],mx[N][30];
void dfs(ll u,ll f)
{
dep[u]=dep[f]+1;
fa[u][0]=f;
for(int i=1;i<=lg[dep[u]];i++)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=head[u];i;i=next[i])
{
ll v=e[i].v;
if(v==f)continue;
mx[v][0]=e[i].w;
dfs(v,u);
}
}
void mxp()
{
for(int j=1;j<=lg[n];j++)
{
for(int i=1;i<=n;i++)
{
mx[i][j]=min(mx[i][j-1],mx[fa[i][j-1]][j-1]);
}
}
}
ll f[N];
ll fd(ll a)
{
if(f[a]==a)return a;
else return f[a]=fd(f[a]);
}
void uni(ll a,ll b)
{
ll x=fd(a),y=fd(b);
f[y]=x;
}
void kruskal()
{
sort(t+1,t+m+1,cmp);
memset(head,0,sizeof head);
tot=0;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)
{
ll a=t[i].u,b=t[i].v,c=t[i].w;
if(fd(a)!=fd(b))
{
uni(a,b);
add(a,b,c);
add(b,a,c);
}
}
}
ll lca(ll a,ll b)
{
ll res=1000000000000000000;
if(dep[a]<dep[b])swap(a,b);
while(dep[a]>dep[b])
{
res=min(res,mx[a][lg[dep[a]-dep[b]]]);
a=fa[a][lg[dep[a]-dep[b]]];
}
if(a==b)return res;
for(int i=lg[dep[a]];i>=0;i--)
{
if(fa[a][i]!=fa[b][i])
{
res=min(res,mx[a][i]);
res=min(res,mx[b][i]);
a=fa[a][i];
b=fa[b][i];
}
}
res=min(res,mx[a][0]);
res=min(res,mx[b][0]);
return res;
}
ZZ_zuozhe
{
//freopen("owo.in","r",stdin);
//freopen("awa.out","w",stdout);
scanf("%lld%lld",&n,&m);
lgp();
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&t[i].u,&t[i].v,&t[i].w);
}
kruskal();
dep[0]=0;
for(int i=1;i<=n;i++)if(!dep[i])dfs(i,0);
mxp();
scanf("%lld",&q);
for(int i=1;i<=q;i++)
{
scanf("%lld%lld",&a,&b);
if(fd(a)!=fd(b))puts("-1");
else printf("%lld
",lca(a,b));
}
return 0;
}
bzoj3306 树
就是遥远的国度嘛(qaq)
这篇博客里有思路和树剖的版本，这里给出倍增方法的
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ZZ_zuozhe int main()
#define N 200005
ll n,q,a,b,root,rt;
char ch[3];
struct edge
{
ll u,v;
}e[N];
ll tot=0,head[N],next[N];
void add(ll a,ll b)
{
++tot;
e[tot].u=a;
e[tot].v=b;
next[tot]=head[a];
head[a]=tot;
}
ll lg[N];
void lgp()
{
for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
}
ll dep[N],fa[N][30];
ll l[N],r[N],cnt=0;
ll num[N],w[N];
void dfs(ll u,ll f)
{
l[u]=++cnt;
num[l[u]]=w[u];
fa[u][0]=f;
dep[u]=dep[f]+1;
for(int i=1;i<=lg[dep[u]];i++)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=head[u];i;i=next[i])
{
ll v=e[i].v;
if(v==f)continue;
dfs(v,u);
}
r[u]=cnt;
}
ll lca(ll a,ll b)
{
if(dep[a]<dep[b])swap(a,b);
while(dep[a]>dep[b])
{
a=fa[a][lg[dep[a]-dep[b]]];
}
if(a==b)return a;
for(int i=lg[dep[a]];i>=0;i--)
{
if(fa[a][i]!=fa[b][i])
{
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
ll tree[N<<2];
void upd(ll rt)
{
tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}
void build(ll rt,ll l,ll r)
{
if(l==r)
{
tree[rt]=num[l];//cout<<l<<' '<<tree[rt]<<endl;
return;
}
ll m=(l+r)>>1;
build(lson);
build(rson);
upd(rt);
}
void change(ll rt,ll l,ll r,ll n,ll val)
{
if(l==r)
{
tree[rt]=val;
return;
}
ll m=(l+r)>>1;
if(m>=n)change(lson,n,val);
if(m<n)change(rson,n,val);
upd(rt);
}
ll query(ll rt,ll l,ll r,ll nl,ll nr)
{
if(nl<=l&&r<=nr)
{
//cout<<' '<<tree[rt]<<endl;
return tree[rt];
}
ll m=(l+r)>>1;
ll ans=1000000000000000000;
if(m>=nl)ans=min(ans,query(lson,nl,nr));
if(m<nr)ans=min(ans,query(rson,nl,nr));
return ans;
}
ZZ_zuozhe
{
//freopen("owo.in","r",stdin);
scanf("%lld%lld",&n,&q);
lgp();
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&a,&w[i]);
if(a)add(a,i);
if(a==0)root=i;
}
dfs(root,0);
rt=root;
build(1,1,n);
for(int i=1;i<=q;i++)
{
scanf("%s",ch);
if(ch[0]=='V')
{
scanf("%lld%lld",&a,&b);
//cout<<' '<<l[a]<<' '<<b<<endl;
change(1,1,n,l[a],b);
}
else if(ch[0]=='E')
{
scanf("%lld",&rt);
}
else if(ch[0]=='Q')
{
scanf("%lld",&a);
//cout<<' '<<a<<' '<<rt<<endl;
if(a==rt)printf("%lld
",tree[1]);
else if(l[a]>l[rt]||r[a]<l[rt])printf("%lld
",query(1,1,n,l[a],r[a]));
else
{
ll now=rt;
for(int i=16;i>=0;i--)
{
if(dep[fa[now][i]]>dep[a])now=fa[now][i];
}
printf("%lld
",min(query(1,1,n,1,l[now]-1),query(1,1,n,r[now]+1,n)));
}
}
}
}