BZOJ5279: [Usaco2018 Open]Disruption-白红宇

BZOJ5279: [Usaco2018 Open]Disruption

阅读量：6670 次

发布时间：2019-06-25

本文共 2528 字，大约阅读时间需要 8 分钟。

题目大意：给你一棵n个节点的树，这n条边称为原边，另给出m条带权值的额外边，求删去每条原边后通过给出的m额外条边变回一棵树的最小价值。

题解：

看完题面以为是Tarjan连通性之类的题目，冷静分析后想到是树链剖分，自己真是Too young too simple。

首先将这棵树进行树链剖分，对于每条额外边x-y，可以作为原树上x-y的路径上的任意一条边删去时的答案，所以路径更新最小值即可。

树链剖分+线段树维护区间最小值，边权转点权的技巧直接把这条边的权值赋到儿子节点上，查找更新时不找LCA即可。。。

输出要求是按原边的顺序，这里用了一个小技巧，大家手模感性理解一下就好了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             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
             
              void read(T1 &r_e_a_d);template
              
               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
               
                >1; if (x<=mid) qwq=min(qwq,query(k<<1,l,mid,x,y)); if (mid
                
                 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
                 
                  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'); } }}

转载于:https://www.cnblogs.com/DFTMR/p/10777093.html

你可能感兴趣的文章