中石油6346 Disruption（LCA 利用倍增思想维护树上最小值）

问题 H: Disruption

时间限制: 1 Sec  内存限制: 128 MB

提交: 12  解决: 3

[提交] [状态] [讨论版] [命题人:admin]

题目描述

Farmer John prides himself on running a well-connected farm. The farm is a collection of N pastures (2≤N≤50,000), pairs of which are connected with N−1 bi-directional pathways, each having unit length. Farmer John notices that using an appropriate series of these pathways, it is possible to travel from any pasture to any other pasture.

Although FJ's farm is connected, he worries what might happen if one of the pathways gets blocked, as this would effectively partition his farm into two disjoint sets of pastures, where the cows could travel within each set but not between the sets. FJ therefore builds a set of M additional bi-directional pathways (1≤M≤50,000), each with a positive integer length at most 109. The cows still only use the original pathways for transit, unless one of these becomes blocked.

If one of the original pathways becomes blocked, the farm becomes partitioned into two disjoint pieces, and FJ will select from among his extra pathways a single replacement pathway that re-establishes connectivity between these two pieces, so the cows can once again travel from any pasture to any other pasture.

For each of the original pathways on the farm, help FJ select the shortest suitable replacement pathway.

输入

The first line of input contains N and M. Each of the next N−1 lines describes an original pathway using integers pp, qq, where p≠q are the pastures connected by the pathway (in the range 1…N). The remaining M lines each describe an extra pathway in terms of three integers: p, q, and r, where r is the length of the pathway. At most one pathway runs between any pair of pastures.

输出

For each of the N−1 original pathways in the order they appear in the input, output the length of the shortest suitable replacement pathway which would re-connect the farm if that original pathway were to be blocked. If no suitable replacement exists, output -1.

样例输入

6 3
1 2
1 3
4 1
4 5
6 5
2 3 7
3 6 8
6 4 5
           

样例输出

7
7
8
5
5
           

【题意】

给出一个n点n-1边的树。然后给出m条可以备用的附加边，并有长度。假如现在树上第i条边抹掉，那么整个树会变成两个连通块，这时候你可以借助任意的附加边来把这两个联通块连接起来。问抹掉第i条边时，利用附加边连接两个联通块的最短距离？

【分析】

易知树上两点之间的路径是唯一的。对于树上的某个边 j ，可能有多条附加边跨过 j ，这些边的最小长度就是抹掉边 j 时的答案（连接两连通块的最小长度）

令1为树的根，在树上做倍增祖先。anc[x][i]代表点x的第1<<i级祖先

令数组Min[x][i]表示点x到第1<<i级祖先之间，被附加边覆盖的最小值。注意！不是x到1<<i级祖先之间边的最小值！！

可以理解为，Min[x][i]是完全覆盖他的所有附加边的最小值

（或者说是，把每一个附加边分解成了2的次幂长度，比如附加边u-v，在树上uv距离为7，则把附加边分解成三段，长度分别为1,2,4）！！

对于m条附加边，我们依次通过LCA去更新Min数组。

最后得到的Min[][]需要进行处理，因为对于Min[x][i]，它覆盖了Min[x][i-1]和Min[father[x]][i-1]两个区间，若Min[x][i]小于后两者，则可以更新后两者，使其更小

最后，每一个点对应的Min[x][0]就是点x到其父结点的边 的答案

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int MAX=1e5+5;
const int INF=0x3f3f3f3f;

struct node{
    int t,next,id;
}e[MAX];
int head[MAX],cnt;
void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;
}
void add(int u,int v,int id)
{
    e[cnt]=node{v,head[u],id};
    head[u]=cnt++;
}
int ans[MAX];
int fa[MAX];//father side
int d[MAX];//deep
int anc[MAX][21];
int Min[MAX][21]; //倍增最小值
void dfs(int x,int father=0)
{
    anc[x][0]=father;
    Min[x][0]=INF;
    for(int i=1;i<=20;i++)
    {
        anc[x][i]=anc[anc[x][i-1]][i-1];
        Min[x][i]=INF;
    }
    for(int i=head[x];~i;i=e[i].next)
    {
        int &t=e[i].t;
        if(t!=father)
        {
            fa[t]=e[i].id;
            d[t]=d[x]+1;
            dfs(t,x);
        }
    }
}
int LCA(int u,int v,int len)
{
    if(d[u]<d[v])swap(u,v);
    for(int i=20;i>=0;i--)
        if(d[anc[u][i]]>=d[v])//u的祖先深于v
        {
            Min[u][i]=min(Min[u][i],len); //更新最小值
            u=anc[u][i];
        }
    if(u==v)return u;
    for(int i=20;i>=0;i--)
        if(anc[u][i]!=anc[v][i])
        {
            Min[u][i]=min(Min[u][i],len); //更新 
            Min[v][i]=min(Min[v][i],len);
            u=anc[u][i];
            v=anc[v][i];
        }
    Min[u][0]=min(Min[u][0],len); //因为最后一次的边在上面循环里访问不到，所以单独处理 
    Min[v][0]=min(Min[v][0],len);
    return anc[u][0];
}
int main()
{
    init();
    int n,m,u,v,len;
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v,i);
        add(v,u,i);
    }
    d[1]=1;
    dfs(1); //倍增祖先处理 
    while(m--)
    {
        scanf("%d%d%d",&u,&v,&len);
        LCA(u,v,len); //更新min
    }

    for(int j=20;j>0;j--)
    {
        for(int i=1;i<=n;i++)
        {
            Min[i][j-1]=min(Min[i][j-1],Min[i][j]);
            Min[anc[i][j-1]][j-1]=min(Min[anc[i][j-1]][j-1],Min[i][j]);
        }
    }
    
    for(int i=2;i<=n;i++)ans[fa[i]]=Min[i][0];
    for(int i=1;i<n;i++)
    {
        if(ans[i]==INF)ans[i]=-1;
        printf("%d\n",ans[i]);
    }
}
/*
8 3
1 2
2 3
3 4
1 5
3 6
2 7
6 8
3 3 10
4 7 2
1 8 5
*/