题目大意:给定一颗树(V,E),将他复制成k棵一模一样的树,然后在这k个树之间加上一些边,最后求两个点之间的最短距离,这题一看直接跑最短路不就行了吗?(太天真了).一看数据,树大小时2e5级别的,k < 50000,这么大的图存都存不下来,更别提跑最短路了,经过仔细观察后发现(没其他想法了…)m很小啊,只有1e4,这就启发我们只记录一部分的点,具体是哪些点呢? 先想一下怎么能够把一颗树的基本形态保存下来的同时只存下我需要的点呢?开始一直想不到好的方法,我当时的思路时这样的,先找到每棵树要存的点,然后在他们之间建边,直接建的时间复杂度时$O(n^2)$,我当时想到了把他们之间的lca也加进去,然后没想到更好的做法,其实我想到那里已经很接近正确答案了,但是不知道具体怎么实现,翻阅题解时发现有种专门做这类问题的做法虚树,这个算法保证将树的结构存下来的同时还能包括所有的重要点(我们真正需要的点),具体做法网上有很多其实就是我上面说的把lca也加上,知道这些我们就可以解出来这个问题了.(下面用到的除虚树以外的y总都讲过了)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 5e5 + 10;
int h[N],e[N],ne[N],w[N],idx;
int dfn[N],dep[N],timestamp;
vector<int> path[N];
map<PII,int> mp;
map<PII,bool> mp1;
int f[N][20];
int q[N];
int stk[N],top;
int n,m,k;
int root;
bool st[N];
int dist[N];
int cnt;
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}
void add_edges(int a,int b,int c)
{
    add(a,b,c);
    add(b,a,c);
}
void dfs_dfn(int u,int fa)
{
    dfn[u] = ++ timestamp;
    //cout << u << endl;
    for(int i = h[u];i != -1;i = ne[i])
    {
        int j = e[i];
        if(j == fa)continue;
        dfs_dfn(j,u);
    }
}
void bfs(int start)
{
    memset(dep,0x3f,sizeof dep);
    int tt = -1,hh = 0;
    dep[0] = 0,dep[start] = 1;
    q[++ tt] = start;
    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            if(dep[j] > dep[t] + 1){
                q[++ tt] = j;
                dep[j] = dep[t] + 1;
                f[j][0] = t;
                //cout << t << endl;
                for(int k = 1;k < 17;k ++)
                {
                    f[j][k] = f[f[j][k - 1]][k - 1];
                }
            }
        }
    }
}
int LCA(int a,int b)
{
    if(dep[a] < dep[b])swap(a,b);
    for(int i = 17;i >= 0;i --)
    {
        if(dep[f[a][i]] >= dep[b])
            a = f[a][i];
    }
    if(a == b)return a;
    for(int i = 17;i >= 0;i --)
    {
        if(f[a][i] ^ f[b][i]){
            a = f[a][i];
            b = f[b][i];
        }
    }
    return f[a][0];
}
void insert(int x)
{
    if(top == 1){
        stk[++ top] = x;
        return ;
    }
    int lca = LCA(stk[top],x);
    //cout << stk[top] << ' ' << x << ' ' << lca << endl;
    while(top > 1 && dfn[stk[top - 1]] >= dfn[lca]){
        if(!mp.count({root,stk[top]}))mp[{root,stk[top]}] = ++ cnt;
        if(!mp.count({root,stk[top - 1]}))mp[{root,stk[top - 1]}] = ++ cnt;
        int t1 = mp[{root,stk[top]}];
        int t2 = mp[{root,stk[top - 1]}];
        add_edges(t1,t2,abs(dep[stk[top - 1]] - dep[stk[top]]));
        //cout << abs(dep[stk[top - 1]] - dep[stk[top]]) << endl;
        top --;
    }
    if(dfn[stk[top]] != dfn[lca]){
        if(!mp.count({root,stk[top]}))mp[{root,stk[top]}] = ++ cnt;
        if(!mp.count({root,lca}))mp[{root,lca}] = ++ cnt;
        int t1 = mp[{root,stk[top]}];
        int t2 = mp[{root,lca}];
        add_edges(t1,t2,abs(dep[lca] - dep[stk[top]]));
        stk[top] = lca;
    }
    stk[++ top] = x;
}
bool cmp(int a,int b)
{
    return dfn[a] < dfn[b];
}
void dijkstra(int start)
{
    memset(dist,0x3f,sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    dist[start] = 0;
    heap.push({0,start});
    while(heap.size())
    {
        PII t = heap.top();
        heap.pop();
        st[t.second] = true;
        for(int i = h[t.second];i != -1;i = ne[i])
        {
            int j = e[i];
            if(st[j])continue;
            if(dist[j] > dist[t.second] + w[i])
            {
                dist[j] = dist[t.second] + w[i];
                heap.push({dist[j],j});
            }
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    memset(h,-1,sizeof h);
    int a,b;
    for(int i = 1;i < n;i ++)
    {
        scanf("%d%d",&a,&b);
        add_edges(a,b,1);
    }
    dfs_dfn(1,-1);
    bfs(1);
    memset(h,-1,sizeof h);
    idx = 0;
    int sa,sb,ta,tb;
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d%d%d%d",&sa,&sb,&ta,&tb);
        if(!mp.count({sa,sb})){
            path[sa].push_back(sb);
            mp[{sa,sb}] = ++ cnt;
        }
        if(!mp.count({ta,tb})){
            path[ta].push_back(tb);
            mp[{ta,tb}] = ++ cnt;
        }
        int t1 = mp[{sa,sb}],t2 = mp[{ta,tb}];
        if(!mp1[{t1,t2}]){
            mp1[{t1,t2}] = mp1[{t2,t1}] = true;
            add_edges(t1,t2,1);
        }
    }
    cin >> sa >> sb >> ta >> tb;
    int start,ed;
    if(!mp[{sa,sb}])mp[{sa,sb}] = ++ cnt;
    if(!mp[{ta,tb}])mp[{ta,tb}] = ++ cnt;
    path[sa].push_back(sb);
    path[ta].push_back(tb);
    start = mp[{sa,sb}];
    ed = mp[{ta,tb}];
    for(int i = 1;i <= k;i ++)
    {
        if(path[i].size() > 0){
            root = i;
            // 加内部边构建虚树
            sort(path[i].begin(),path[i].end(),cmp);
            //for(auto p : path[i])cout << p << ' ';
            stk[top = 1] = 1;
            for(int j = 0;j < (int)path[i].size();j ++)
                insert(path[i][j]);
                while(top > 1){
                    if(!mp.count({root,stk[top]}))mp[{root,stk[top]}] = ++ cnt;
                    if(!mp.count({root,stk[top - 1]}))mp[{root,stk[top - 1]}] = ++ cnt;
                    int t1 = mp[{root,stk[top]}];
                    int t2 = mp[{root,stk[top - 1]}];
                    add_edges(t1,t2,abs(dep[stk[top - 1]] - dep[stk[top]]));
                    top --;
                }
        }
    }
    dijkstra(start);
    if(dist[ed] >= 0x3f3f3f3f)cout << -1 << endl;
    else cout << dist[ed] << endl;
    return 0;
}