题目描述

题目描述

$Farmer\ John$自豪于他所经营的交通发达的的农场。这个农场是由$N$块牧场（$2 \leq N \leq 50,000$）组成的，$N-1$条双向道路将它们连接起来，每一条道路的都为一单位长度。$Farmer\ John$注意到，从任何一块牧场到另一块牧场，都能通过一组合适的道路到达。

尽管$FJ$的农场现在是连通的，他担心如果有一条道路被阻断会发生什么，因为这事实上会将他的农场分为两个不相交的牧场集合，奶牛们只能够在每一个集合内移动但不能在集合间移动。于是$FJ$又建造了$M$条额外的双向道路（$1 \leq M \leq 50,000$），每一条的长度都是一个至多为$10^9$的正整数。奶牛们仍然可以使用原有的道路进行移动，除非其中的某些被阻断了。

如果某条原有的道路被阻断了，农场就会被分为两块不相交的区域，那么$FJ$就会从他的额外修建的道路中选择一条能够重建这两块区域的连通性的，取代原来那条，从而奶牛们又可以从任何一块牧场去往另一块牧场。

对于农场上每一条原有的道路，帮助$FJ$选出最短的替代用的道路。

输入输出格式

输入格式：

输入的第一行包含$N$和$M$。接下来的$N-1$行，每行用整数$p$和$q$描述了一条原有的道路，其中$p \ne q$是这条道路连接的两块牧场（在$1 \ldots N$范围内）。剩下的$M$行，每行用三个整数$p$、$q$和$r$描述了一条额外的道路，其中$r$是这条道路的长度。任何两块牧场之间至多只有一条道路。

输出格式：

对原有的$N−1$条道路的每一条，按照它们在输入中出现的顺序，输出如果这条道路被阻断的话，能够重新连接农场的最短的替代用道路的长度。如果不存在合适的替代用的道路，输出$-1$。

输入输出样例

输入样例#1：

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

输出样例#1：

7
7
8
5
5

解题思路

树链剖分

经过比较仔细的分析，还是可以得出一条变删掉之后，加入的那条边必能使树重新联通，那么加入的这条边的两端点，在原树上的路径必经过那条删掉的边，$RT \downarrow$

Code

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define rgt register
#define N 50010
using namespace std;
struct node{
    int to,nxt;
}b[N<<1];
int head[N],seg[N],top[N],f[N<<2];
int deep[N],Sz[N],son[N],fa[N];
int n,m,t,x,y,num,L,R,res,ans;
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void add(rgt int x,rgt int y) {
    b[++t].to=y,b[t].nxt=head[x],head[x]=t;
    b[++t].to=x,b[t].nxt=head[y],head[y]=t;
}
inline void dfs1(rgt int k) {
    rgt int i,to;
    deep[k]=deep[fa[k]]+1,Sz[k]=1;
    for(i=head[k];i;i=b[i].nxt)
    {
        to=b[i].to;
        if(to==fa[k]) continue;
        fa[to]=k,dfs1(to);
        Sz[k]+=Sz[to];
        if(Sz[to]>Sz[son[k]])
            son[k]=to;
    }
}
inline void dfs2(rgt int k) {
    if(son[k])
    {
        seg[son[k]]=++num;
        top[son[k]]=top[k];
        dfs2(son[k]);
    }
    rgt int i,to;
    for(i=head[k];i;i=b[i].nxt)
    {
        to=b[i].to;
        if(top[to]) continue;
        seg[to]=++num;
        top[to]=to;
        dfs2(to);
    }
}
inline void push(rgt int k) {//其实一个数组就够了，就是特判有点复杂
    int cur=k<<1;
    f[cur]=min(f[cur],f[k]);
    f[cur|1]=min(f[cur|1],f[k]);
    f[k]=INF;//下传后初值要变成INF
}
inline void Modify(rgt int k,rgt int l,rgt int r) {
    if(f[k]!=INF&&l!=r) push(k);
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {
        f[k]=min(f[k],res);
        if(l!=r) push(k);
        return;
    }
    rgt int mid=(l+r)>>1,cur=k<<1;
    Modify(cur,l,mid);
    Modify(cur|1,mid+1,r);
}
#define fx top[x]
#define fy top[y]
inline void Add(int x,int y) {
    while(fx!=fy) {
        if(deep[fx]<deep[fy]) swap(x,y);
        L=seg[fx],R=seg[x];
        Modify(1,1,n);
        x=fa[fx];
    }
    if(deep[x]<deep[y]) swap(x,y);
    L=seg[y]+1,R=seg[x];
    Modify(1,1,n);
    return;
}
inline void Query(rgt int k,rgt int l,rgt int r) {
    if(f[k]!=INF&&l!=r) push(k);
    if(l==r&&l==L) {ans=f[k];return;}
    rgt int mid=(l+r)>>1,cur=k<<1;
    if(L<=mid) Query(cur,l,mid);
    else Query(cur|1,mid+1,r);
}
int main()
{
    int i;
    n=read(),m=read();
    for(i=1;i<n;i++)
        x=read(),y=read(),add(x,y);
    num=seg[1]=top[1]=1;
    dfs1(1),dfs2(1);
    memset(f,INF,sizeof(f));//注意一开始的初始化
    for(i=1;i<=m;i++)
    {
        x=read(),y=read(),res=read();
        Add(x,y);
    }
    for(i=1;i<t;i+=2)
    {
        x=b[i+1].to,y=b[i].to;
        if(deep[x]>deep[y]) L=seg[x];
        else L=seg[y];
        Query(1,1,n);
        if(ans!=INF) printf("%d\n",ans);
        else printf("-1\n");
    }
    return 0;
}

devil.