题解 P3894 【[GDOI2014]传送】

· · 题解

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

分类讨论： ## **第一种情况：** $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;
}