良心送分题【牛客挑战赛35 E】【LCA处理+最短路】

先发一下我的CSDN博客哟：https://blog.csdn.net/qq_41730082/article/details/103643159
首先，这道题的思维展开，肯定不能把所有的点都用进来，那么，选择的点，我们可以只考虑起点和终点还有特殊的像M条链接边的点了，所以，点数的上限就是1e5，而不是2e10了，这就是对于点的优化了。

再者，比赛的时候我处理这1e5个点的时候用了两两平方的方式来求LCA，尝试着卡数据随机……但是很显然，这次的数据造的很用心，这样的做法确实被卡掉了，于是就是想办法去优化这个求LCA的过程。

我们可以知道，最后的时候1～K棵树都会分布着一些点，那么的话，我们就是要去对点进行操作即可，首先，当仁不让的就是1号根结点，如有必要是一定要放进来的。其次再看，我们可以把一些打了标记（也就是M条边中用到的点给放进来处理），我这里用了他们的dfs序来进行维护。

说到为什么要用dfs序，我的目的是为了保证它们尽可能的是在一条链上，或者就是链之间的转换了，所以就保证了点的数量最多是在1e5的基础上翻倍而已。

按照dfs序我们有序的进行操作，首先从根结点开始，我们可以知道的是，如果在同一条链上的时候，我们就可以直接增加了，因为它的深度一定是更浅的并且它的LCA一定是到更浅的两个之一的点。如果在两个不同的链上的时候，我们肯定会找到它们的LCA，这时候这时候，我们判断它与前两个的关系，看是否可以继续往上缩这样的过程。这块处理的时间复杂度是O(M*log(N))。

然后，我们已经把点和边都处理出来了，从起点开始像终点跑Dijkstra即可，此处的时间复杂度是O(N*log(N))，所以总的时间复杂度就满足条件了。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define _ABS(x, y) ( x > y ? (x - y) : (y - x) )
#define lowbit(x) ( x&( -x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f3f3f3f3f
#define efs 1e-7
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
//const int maxN = 1e6 + 7;
int N, M, K, head[200005], cnt, S_beg, T_end;
struct Tree_Eddge
{
    int nex, to;
    Tree_Eddge(int a=-1, int b=0):nex(a), to(b) {}
}Tree_edge[400005];
inline void Tree_addEddge(int u, int v)
{
    Tree_edge[cnt] = Tree_Eddge(head[u], v);
    head[u] = cnt++;
}
inline void Tree_add(int u, int v) { Tree_addEddge(u, v); Tree_addEddge(v, u); }
int dfn[200005], _Index, root[200005][19], deep[200005];
//LCA部分
void LCA_dfs(int u, int fa)
{
    root[u][0] = fa;
    deep[u] = deep[fa] + 1;
    dfn[u] = ++_Index;
    for(int i=0; i<log2(1. * N); i++) { root[u][i + 1] = root[root[u][i]][i]; }
    for(int i=head[u], v; ~i; i=Tree_edge[i].nex)
    {
        v = Tree_edge[i].to;
        if(v == fa) continue;
        LCA_dfs(v, u);
    }
}
inline int _LCA(int u, int v)
{
    if(deep[u] < deep[v]) swap(u, v);
    int det = deep[u] - deep[v];
    for(int i=log2(det); i>=0; i--)
    {
        if((det >> i) & 1) u = root[u][i];
    }
    if(u == v) return u;
    for(int i=log2(N); i>=0; i--)
    {
        if(root[u][i] ^ root[v][i])
        {
            u = root[u][i];
            v = root[v][i];
        }
    }
    return root[u][0];
}
//建立新图部分，保证点数量
map<int, int> V[50004];
map<int, int>::iterator it;
int new_id;
inline int Hash_map_id(int k_id, int t_id)
{
    if(!V[k_id][t_id]) V[k_id][t_id] = ++new_id;
    return V[k_id][t_id];
}
int new_head[500005], new_cnt;
struct new_Eddge
{
    int nex, to, val;
    new_Eddge(int a=-1, int b=0, int c=0):nex(a), to(b), val(c) {}
}new_edge[1000006];
inline void new_addEddge(int u, int v, int w)
{
    new_edge[new_cnt] = new_Eddge(new_head[u], v, w);
    new_head[u] = new_cnt++;
}
inline void new_add(int u, int v, int w) { new_addEddge(u, v, w); new_addEddge(v, u, w); }
pair<int, int> a[100005], que[100005];
int a_num, top;
inline bool cmp(pair<int, int> e1, pair<int, int> e2) { return dfn[e1.first] < dfn[e2.first]; }
inline void Insert_Point(int kid, pair<int, int> x) //开始放点进去了
{
    if(top < 2)
    {
        que[++top] = x;
        return;
    }
    int lca = _LCA(que[top].first, x.first);
    while(top > 1 && dfn[lca] <= dfn[que[top - 1].first])
    {
        new_add(que[top].second, que[top - 1].second, deep[que[top].first] - deep[que[top - 1].first]);
        top--;
    }
    if((lca ^ que[top].first) && top > 1)
    {
        new_add(que[top].second, Hash_map_id(kid, lca), deep[que[top].first] - deep[lca]);
        que[top] = MP(lca, Hash_map_id(kid, lca));
    }
    que[++top] = x;
}
inline void new_Graph_Build()   //建立新图过程
{
    for(int ki=1; ki<=K; ki++) //有K棵子树
    {
        a_num = top = 0;
        Hash_map_id(ki, 1);
        for(it = V[ki].begin(); it != V[ki].end(); it++)
        {
            a[++a_num] = *it;
        }
        sort(a + 1, a + a_num + 1, cmp);
        for(int i=1; i<=a_num; i++) Insert_Point(ki, a[i]);
        while(top > 1)
        {
            new_add(que[top].second, que[top - 1].second, deep[que[top].first] - deep[que[top - 1].first]);
            top --;
        }
    }
}
//Dijkstra跑最短路
struct node
{
    int id; ll val;
    node(int a = 0, ll b = 0):id(a), val(b) {}
    friend bool operator < (node e1, node e2) { return e1.val > e2.val; }
};
ll dis[500006];
inline void Dijkstra()
{
    for(int i=1; i<=new_id; i++) dis[i] = INF;
    dis[S_beg] = 0;
    priority_queue<node> Q;
    Q.push(node(S_beg, 0));
    node now;
    while(!Q.empty())
    {
        now = Q.top(); Q.pop();
        int u = now.id;
        if(now.val > dis[u]) continue;
        for(int i=new_head[u], v; ~i; i=new_edge[i].nex)
        {
            v = new_edge[i].to; ll w = new_edge[i].val;
            if(dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                Q.push(node(v, dis[v]));
            }
        }
    }
    printf("%lld\n", dis[T_end] < INF ? dis[T_end] : -1);
}
inline void init()
{
    cnt = new_cnt = new_id = 0;
    for(int i=1; i<=N; i++) head[i] = -1;
    memset(new_head, -1, sizeof(new_head));
}
int main()
{
    scanf("%d%d%d", &N, &M, &K);
    init();
    for(int i=1, u, v; i<N; i++)    //建立初始化树
    {
        scanf("%d%d", &u, &v);
        Tree_add(u, v);
    }
    LCA_dfs(1, 0);
    int k1, t1, k2, t2;
    for(int i=1; i<=M; i++)
    {
        scanf("%d%d%d%d", &k1, &t1, &k2, &t2);
        new_add(Hash_map_id(k1, t1), Hash_map_id(k2, t2), 1);
    }
    scanf("%d%d%d%d", &k1, &t1, &k2, &t2);
    S_beg = Hash_map_id(k1, t1); T_end = Hash_map_id(k2, t2);
    new_Graph_Build();
    Dijkstra();
    return 0;
}
/*
12 3 1
1 2
2 3
2 4
2 5
3 6
3 7
3 8
8 9
9 10
9 11
10 12
1 5 1 8
1 4 1 10
1 11 1 12
1 1 1 12
*/