BZOJ5279: [Usaco2018 Open]Disruption
题目大意：给你一棵n个节点的树，这n条边称为原边，另给出m条带权值的额外边，求删去每条原边后通过给出的m额外条边变回一棵树的最小价值。
题解：
看完题面以为是Tarjan连通性之类的题目，冷静分析后想到是树链剖分，自己真是Too young too simple。
首先将这棵树进行树链剖分，对于每条额外边x-y，可以作为原树上x-y的路径上的任意一条边删去时的答案，所以路径更新最小值即可。
树链剖分+线段树维护区间最小值，边权转点权的技巧直接把这条边的权值赋到儿子节点上，查找更新时不找LCA即可。。。
输出要求是按原边的顺序，这里用了一个小技巧，大家手模感性理解一下就好了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<iostream>
#include<queue>
using namespace std;
#define isNum(a) (a>='0'&&a<='9')
#define SP putchar(' ')
#define EL putchar('\n')
#define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
template<class T1>void read(T1 &r_e_a_d);
template<class T1>void write(T1 w_r_i_t_e);
const int N=50005;
int n,m,len=1,x,y,z,a[N],head[N],idn[N],idw[N];
struct EDGE{
int to,next,id;
}edge[N<<1];
void add(int x,int y,int d){
++len;
edge[len].to=y;edge[len].next=head[x];edge[len].id=d;head[x]=len;
}
int dep[N],son[N],siz[N],fa[N];
void dfs1(int u,int father){
dep[u]=dep[father]+1;fa[u]=father;siz[u]=1;
for (register int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if (v!=father){
dfs1(v,u);siz[u]+=siz[v];
if (son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
idn[v]=edge[i].id;
}
}
}
int tot,top[N],dfn[N],seg[N];
void dfs2(int u,int tp){
top[u]=tp;
dfn[u]=++tot;
seg[dfn[u]]=u;
if (son[u]==-1) return ;
dfs2(son[u],tp);
for (register int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if (v!=fa[u]&&v!=son[u]){
dfs2(v,v);
}
}
}
int tree[50005<<2],lazy[50005<<2];
void build(int k,int l,int r){
tree[k]=lazy[k]=1<<30;
if (l==r) return ;
int mid=l+r>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void pushdown(int k){
tree[k<<1]=min(tree[k<<1],lazy[k]);
tree[k<<1|1]=min(tree[k<<1|1],lazy[k]);
lazy[k<<1]=min(lazy[k],lazy[k<<1]);
lazy[k<<1|1]=min(lazy[k],lazy[k<<1|1]);
lazy[k]=1<<30;
}
void modify(int k,int l,int r,int x,int y,int z){
if (x<=l&&r<=y){
tree[k]=min(tree[k],z);
lazy[k]=min(lazy[k],z);
return ;
}
if (lazy[k]!=1<<30) pushdown(k);
int mid=l+r>>1;
if (x<=mid) modify(k<<1,l,mid,x,y,z);
if (mid<y) modify(k<<1|1,mid+1,r,x,y,z);
tree[k]=min(tree[k<<1],tree[k<<1|1]);
}
int query(int k,int l,int r,int x,int y){
if (x<=l&&r<=y){
return tree[k];
}
if (lazy[k]!=1<<30) pushdown(k);
int qwq=1<<30,mid=l+r>>1;
if (x<=mid) qwq=min(qwq,query(k<<1,l,mid,x,y));
if (mid<y) qwq=min(qwq,query(k<<1|1,mid+1,r,x,y));
return qwq;
}
void solve(int x,int y,int z){
while (top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]]) x^=y^=x^=y;
modify(1,1,n,dfn[top[x]],dfn[x],z);
x=fa[top[x]];
}
if (dep[x]<dep[y]) x^=y^=x^=y;
modify(1,1,n,dfn[y]+1,dfn[x],z);
}
int main(){
memset (son,-1,sizeof (son));
read(n);read(m);
for (register int i=1;i<n;++i){
read(x);read(y);
add(x,y,i);add(y,x,i);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
for (register int i=1;i<=m;++i){
read(x);read(y);read(z);
solve(x,y,z);
}
for (register int i=2;i<=n;++i){
idw[idn[i]]=i;
}
for (register int i=1;i<n;++i){
int ans=query(1,1,n,dfn[idw[i]],dfn[idw[i]]);
if (ans==1<<30) printf ("-1\n");
else write(ans),EL;
}
return 0;
}
template<class T1>void read(T1 &r_e_a_d){
T1 k=0;
char ch=getchar();
int flag=1;
while(!isNum(ch)){
if(ch=='-'){
flag=-1;
}
ch=getchar();
}
while(isNum(ch)){
k=((k<<1)+(k<<3)+ch-'0');
ch=getchar();
}
r_e_a_d=flag*k;
}
template<class T1>void write(T1 w_r_i_t_e){
if(w_r_i_t_e<0){
putchar('-');
write(-w_r_i_t_e);
}else{
if(w_r_i_t_e<10){
putchar(w_r_i_t_e+'0');
}else{
write(w_r_i_t_e/10);
putchar((w_r_i_t_e%10)+'0');
}
}
}
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
更多精彩
