求调，玄关

30pts

台风防范

题目描述

由于频繁有台风登陆，A 国如今受到狂风暴雨的洗礼。在这种恶劣的环境中，保证交通畅通是 A 国王首要关心的事情。A 国当前的交通情况是由 $N-1$ 条双向道路将 $N$ 个城市联通起来，其中每条道路的长度都是 $1$。需要注意，任意两个城市都是可以互相到达的。

A 国王为了应对某条道路阻断后带来的不好的结果，他决定启用备用道路，现在一共有 $M$ 条备用的双向道路，每一条的长度均为一个至多为 $10^9$ 的正整数。人们仍然可以使用未被阻断的原有道路进行移动。

如果某条原有的道路被阻断了，整个国家就会被分为两块不相交的区域，那么 A 国王就会从额外修建的道路中选择一条能够使这两块区域连通的，取代被阻断的那条，从而使得整个国家重新联通起来。

对于 A 国的每一条原有的道路，帮助 A 国王选出最短的替代用的道路。

输入格式

输入的第一行包含 $N$ 和 $M$。

接下来的 $N−1$ 行，每行用整数 $p$ 和 $q$ 描述了一条原有的道路，其中 $p,q$ 是这条道路连接的两个城市。

剩下的 $M$ 行，每行用三个整数 $p,q$ 和 $r$ 描述了一条额外的道路，其中 $r$ 是这条道路的长度。

输出格式

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

提示

对于 $20\%$ 的数据，$2\le N\le 5\times10^3,1\le M\le 1\times10^4$。

对于额外 $20\%$ 的数据，原来所有城市道路构成一条链。

对于 $100\%$ 的数据，$2\le N\le 5\times 10^4,1\le M\le 5\times 10^4,1\le p,q\le N,p \neq q, 0 \le r \le 10^9$。

代码

#include<bits/stdc++.h>
#define lson o<<1
#define rson o<<1|1
#define nmid int mid=(nowr+nowl)>>1;
//#include<ctime>
//#include<windows.h>
using namespace std;
const int maxn=5e4+5;
int n,m;
struct Edge{
    int _this,nxt;
    Edge(){
        _this=nxt=0;
    }
}edge[maxn<<1];
int headnxt[maxn];
int idx;
void merge(int from,int to){
    edge[++idx]._this=to;
    edge[idx].nxt=headnxt[from];
    headnxt[from]=idx;
}
bool vis[maxn];
int fa[maxn],deep[maxn],root[maxn];
int id[maxn];
int tim=1;
void dfs(int f){
    int maxson=-1;
    for(int it=headnxt[f];it;it=edge[it].nxt){
        if(!vis[edge[it]._this]&&edge[it]._this>maxson)
            maxson=edge[it]._this;
    }
    for(int it=headnxt[f];it;it=edge[it].nxt){
        int nowtry=edge[it]._this;
        if(!vis[nowtry]){
            ++tim;
            id[nowtry]=tim;
            vis[nowtry]=1;
            fa[id[nowtry]]=id[f];
            deep[id[nowtry]]=deep[id[f]]+1;
            if(nowtry==maxson){
                root[id[nowtry]]=root[id[f]];
            }
            else root[id[nowtry]]=id[nowtry];
            dfs(nowtry);
        }
    }
}

struct Normedge{
    int s,t,w;
}helpedge[maxn],reqedge[maxn];
bool cmp(Normedge x,Normedge y){return x.w>y.w;}

int t[maxn<<2];
//void push_up(int o){
//  t[o]=min(t[lson],t[rson]);
//}
//void build(int nowl,int nowr,int o){
//  if(nowl==nowr){
//      t[o]=0x3f3f3f3f;
//  }
//  nmid;
//  build(nowl,mid,lson)    
//  build(mid+1,nowr,rson);
//}
void push_down(int o){
    if(t[o]==-1) return;
    t[lson]=t[o];
    t[rson]=t[o];
    t[o]=-1;
}
int query(int nowl,int nowr,int o,int p){
    if(nowl==nowr){
        return t[o];
    }
    nmid;
    push_down(o);
    int res=0;
    if(p<=mid) res=query(nowl,mid,lson,p);
    else res=query(mid+1,nowr,rson,p);
    return res;
}
void update(int nowl,int nowr,int l,int r,int o,int val){
    if(l<=nowl&&nowr<=r){
        t[o]=val;
        return;
    }
    nmid;
    push_down(o);
    if(l<=mid) update(nowl,mid,l,r,lson,val);
    if(r>mid) update(mid+1,nowr,l,r,rson,val);
//  push_up(o);
}
int main(){
//  freopen("typhoon.in","r",stdin);
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i){
        scanf("%d%d",&reqedge[i].s,&reqedge[i].t);
        merge(reqedge[i].s,reqedge[i].t);
        merge(reqedge[i].t,reqedge[i].s);
    }

    id[1]=1;
    fa[id[1]]=-1;
    deep[id[1]]=1;
    root[id[1]]=id[1];
    vis[1]=1;
    dfs(1);//求id（dfn）

    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&helpedge[i].s,&helpedge[i].t,&helpedge[i].w);
    }
    sort(helpedge+1,helpedge+m+1,cmp);
    //插入辅助边

//  DWORD start=GetTickCount(),end;
    memset(t,-1,sizeof t);
    for(int i=1;i<=m;++i){
        int s=helpedge[i].s,e=helpedge[i].t,w=helpedge[i].w;
        s=id[s];
        e=id[e];

        while(root[s]!=root[e]){
            if(deep[root[s]]>deep[root[e]]){
                update(1,n,root[s],s,1,w);
//              cout<<query(1,n,1,5);
                s=fa[root[s]];
            }
            else{
                update(1,n,root[e],e,1,w);
                e=fa[root[e]];
            }
        }
        if(s>e){
            update(1,n,e+1,s,1,w);
        }
        else{
            update(1,n,s+1,e,1,w);
        }   
//      end=GetTickCount();
//      cout<<"t:"<<end-start<<endl;
//      start=GetTickCount();
    }

    for(int i=1;i<n;++i){
        int s=reqedge[i].s,e=reqedge[i].t;
        s=id[s];
        e=id[e];
        if(fa[e]==s) swap(e,s);
        int ans=query(1,n,1,s);
        printf("%d\n",ans);
    }
    return 0;
}

树链剖分+线段覆盖+线段树维护

30pts wa on #1,2,9

tle on #4,7,8,10

拿到了数据，tle 的跑了 7s，可能是常数大了

dalao 帮忙看看能不能优化