51nod 2882最短路 (树链剖分）

我们画个图添加一个非树边 能给树带来什么东西

4 6是非树边 所以对于 4来说除了 2 4 的最短路可以变为 1 - 5 - 6 - 4
对于2来说变为 1 - 5 - 6 - 4 - 2
对于5来说 1 - 2 - 4 - 6 - 5
对于6来说 1 - 2 - 4 - 6
值为dis[u] + dis[v] + dis[u,v] - dis[x] x不能为lca(u,v) 因为若选择这个点我们减去的是dis[lca(u,v)]明显剩下的路径就是一个圈 是错误的
我们只需要找到 dis[u] + dis[v] + dis[u,v]最小即可找到最小的题目要求
明显就是一个树链剖分嘛将树点转化成区间进行操作 复杂度是mlognlogn 所以够了

#include<iostream>
#include<cstring>

using namespace std;

const int N = 4e3 + 10,M = 2e5 + 10;

int head[N],to[M],last[M],w[M],cnt;
void add(int a,int b,int c){
    
    to[++cnt] = b;
    w[cnt] = c;
    last[cnt] = head[a];
    head[a] = cnt;
}

struct Edge{
    
    int u,v,w;
}edge[M];

struct node{
    
    int l,r,minn;
}tree[N * 4];

int edge_cnt;
int sz[N],son[N],fa[N],top[N];
int dep[N],id[N],times,dis[N];
void dfs1(int x,int lastt){
    
    fa[x] = lastt;
    sz[x] = 1;
    dep[x] = dep[lastt] + 1;
    for(int i = head[x]; i != -1; i = last[i]){
    
        int j = to[i];
        if(j != lastt){
    
            dis[j] = dis[x] + w[i];
            dfs1(j,x);
            sz[x] += sz[j];
            if(sz[son[x]] < sz[j]){
    
                son[x] = j;
            }
        }
    }
}

void dfs2(int x,int tp){
    
    id[x] = ++times;
    top[x] = tp;
    if(!son[x]) return;
    dfs2(son[x],tp);
    for(int i = head[x]; i != -1; i = last[i]){
    
        int j = to[i];
        if(j != fa[x] && j != son[x]){
    
            dfs2(j,j);
        }
    }
}

void build(int l,int r,int p){
    
    tree[p].l = l,tree[p].r = r;
    tree[p].minn = 0x3f3f3f3f;
    if(l == r){
    
        return;
    }
    int mid = l + r >> 1;
    build(l,mid,p * 2);
    build(mid + 1,r, p * 2 + 1);
}

void update(int l,int r,int k,int p){
    
    if(tree[p].l >= l && r >= tree[p].r){
    
        tree[p].minn = min(tree[p].minn,k);
        return;
    }
    int mid = tree[p].l + tree[p].r >> 1;
    if(l <= mid) update(l,r,k,p * 2);
    if(mid < r) update(l,r,k,p * 2 + 1);
}

void update_edge(int x,int y,int w){
    
    while(top[x] != top[y]){
    
        if(dep[top[x]] < dep[top[y]])  swap(x,y);
        update(id[top[x]],id[x],w,1);
        x = fa[top[x]];
    }
    if(x == y) return;
    if(dep[x] > dep[y]) swap(x,y);
    update(id[x] + 1,id[y],w,1);
}

int ans[N];
void get_answer(int l,int r,int p){
    
    if(l == r){
    
        ans[l] = tree[p].minn;
        return;
    }
    int mid = l + r >> 1;
    tree[p * 2].minn = min(tree[p * 2].minn,tree[p].minn);
    tree[p * 2 + 1].minn = min(tree[p * 2 + 1].minn,tree[p].minn);
    get_answer(l,mid,p * 2);
    get_answer(mid + 1,r,p * 2 + 1);
}

int main(){
    
    memset(head,-1,sizeof head);
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
    
        int a,b,l,t;
        scanf("%d%d%d%d",&a,&b,&l,&t);
        if(t == 1){
    
            add(a,b,l);
            add(b,a,l);
        }else{
    
            edge[++edge_cnt] = Edge{
    a,b,l};
        }
    }

    dfs1(1,0);
    dfs2(1,1);
    build(1,n,1);

    for(int i = 1; i <= edge_cnt; i++){
    
        update_edge(edge[i].u,edge[i].v,dis[edge[i].u] + dis[edge[i].v] + edge[i].w);
    }

    get_answer(1,n,1);

    for(int i = 2; i <= n; i++){
    
        if(ans[id[i]] != 0x3f3f3f3f) printf("%d ",ans[id[i]] - dis[i]);
        else printf("-1 ");
    }

    return 0;
}