自动搬运

查看原文

来自洛谷，原作者为

	s_r_f 这里是一个只会背板和fst的蒟蒻

搬运于2025-08-24 21:53:49，当前版本为作者最后更新于2019-06-15 18:05:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题的数据好像是错的吧?用省选原数据我是$A$的。。。

$upd:$真的数据已经放在讨论区

分类讨论：

第一种情况： $s0 ≠ e0$

不妨设$s0 < e0$.

容易发现，在区间$[s0+1,e0-1]$的城市中，

我们需要用到传送门，先从$i-1$传送到$i$，再从$i$传送到$i+1$.

所以我们需要找一条最短的 从一个叶子节点到另一个叶子节点 的路径。

这个可以通过树形$DP$，$O(\sum m_i)$ 得出。

然后，我们还需要从$(s0,e0)$走到第$s0$棵树的一个最近的叶子节点,从$(s1,e1)$走到第$s1$棵树的一个最近的叶子节点。

最后统计答案时，三段距离的和 $+$ 传送门使用次数$($即$s1 - s0)$ 就是最短路。

第二种情况： $s0 = e0$

一开始我$naive$了，以为就是树上两点的距离

结果我对拍出错了！

实际上，我就是$naive$了.

设这两个点为$u,v$

我们可以从$u$，走到最近的叶子节点$p_u$

然后传送到另一棵树中，走到另一个叶子节点$($能用的传送门$)$

再用传送门，传送到$v$的最近的叶子节点$p_v$,

然后再走回$v!$

那么$ans$还可以是$u,v$到叶子节点的最近距离之和 $+$ 隔壁的$≤2$棵树上最短的 从一个叶子节点到另一个叶子节点 的路径 $+$ 两次传送的花费$2$.

然后就可以过省选数据了。。。不知道为什么luogu数据过不去

代码:

#include <bits/stdc++.h>
#define LL long long
using namespace std;
inline int read(){
    static int x,f; x = 0,f = 1; static char c; c = getchar();
    while (c != EOF && !isdigit(c)) {if (c == '-') f = -1;c = getchar();}
    while (isdigit(c)) {x = x * 10 + c - '0';c = getchar();}
    return x * f;
}
inline void write(LL x){
    if (x < 0) putchar('-'),x = -x;
    if (x > 9) write(x/10); putchar(x%10+'0');
}
inline void writeln(LL x){ write(x),putchar('\n'); }
const int N = 350005,V = 1000005,E = V<<1;
const LL INF = 1005ll * E;
int To[E],Ne[E],Dis[E],He[V],k;
inline void add(int x,int y,int z){ ++k; To[k] = y,Ne[k] = He[x],Dis[k] = z,He[x] = k; }
int n,l[N],r[N]; LL a[N],v[V],pre[N];
int from[V];

int fa[V],top[V],size[V],son[V],dpt1[V]; LL dpt[V];
LL ww;
void dp(int x,int f,int id){
    v[x] = INF; from[x] = -1; fa[x] = f; dpt1[x] = dpt1[f] + 1;
    size[x] = 1;
    for (int p = He[x],y; p ; p = Ne[p]) if ((y = To[p]) ^ f){
        dpt[y] = dpt[x] + Dis[p];
        dp(y,x,id);
        if ((ww = v[x] + v[y] + Dis[p]) < a[id]) a[id] = ww;
        if ((ww = v[y] + Dis[p]) < v[x]) v[x] = ww,from[x] = from[y];
        size[x] += size[y];
        if (size[y] > size[son[x]]) son[x] = y; 
    }
    if (!son[x]) v[x] = 0,from[x] = x;
}
void dp2(int x,int f,int id,int dd){
    int p,y = f;
    if (y && (from[y] ^ -1) && (from[y] ^ from[x])){
        if ((ww = dd + v[x] + v[y]) < a[id]) a[id] = ww;
        if ((ww = v[y] + dd) < v[x]) v[x] = ww,from[x] = from[y];
    }
    for (p = He[x]; p ; p = Ne[p]) if ((y = To[p]) ^ f) dp2(y,x,id,Dis[p]);
}
void dfs(int x){
    if (son[x]){
        top[son[x]] = top[x],dfs(son[x]);
        for (int p = He[x],y; p ; p = Ne[p]) if (!top[y = To[p]]) top[y] = y,dfs(y);
    }
}
inline int LCA(int x,int y){
    while (top[x] ^ top[y]){ if (dpt1[top[x]] < dpt1[top[y]]) swap(x,y); x = fa[top[x]]; }
    return dpt1[x] <= dpt1[y] ? x : y;
}
inline void Ans(LL ans){ if (ans >= INF) puts("-1"); else writeln(ans); }
int main(){
    int i,s,u,vv,w;
    n = read();
    for (i = 1; i <= n; ++i){
        l[i] = r[i-1] + 1;
        r[i] = l[i] + (s = read()) - 1;
        --s;
        while (s--) u = read() + l[i],vv = read() + l[i],w = read(),add(u,vv,w),add(vv,u,w);
        a[i] = INF;
        dp(l[i],0,i);
        dp2(l[i],0,i,0);
        top[l[i]] = l[i];
        dfs(l[i]);
        pre[i] = pre[i-1] + a[i];
    }
    int q = read(),ql,qu,qr,qv;
    LL ans,ans1;
    a[0] = a[n+1] = INF;
    while (q--){
        ql = read() + 1,qu = read() + l[ql],qr = read() + 1,qv = read() + l[qr];
        if (ql > qr) swap(ql,qr),swap(qu,qv);
        if (ql ^ qr) Ans(qr - ql + v[qu] + v[qv] + pre[qr-1] - pre[ql]);
        else{
            ans = dpt[qu] + dpt[qv] - (dpt[LCA(qu,qv)] << 1);
            if (from[qu] ^ from[qv]){
                ans1 = v[qu] + v[qv] + 2;
                if (ans1 + a[ql-1] < ans) ans = ans1 + a[ql-1];
                if (ans1 + a[ql+1] < ans) ans = ans1 + a[ql+1];
            }
            Ans(ans);
        }
    }
    return 0;
}