题解：P9058 [Ynoi2004] rpmtdq

· · 题解

树上路径，考虑点分治。对于当前根 r，先找出所有的 d_x=\mathrm{dis}(x,r)。则对于任意一条路径 (x,y)，我们用 d_x+d_y 表示其长度。

对于在 r 同一颗子树的 x,y，我们会将其路径算长，但当我们继续递归，一定会算到正确的路径，所以这样做对答案没有影响。

于是我们有若干点对 (x,d_x)，按 x 增序排列。每次求 l \le x,y \le r 的最小的 d_x+d_y，我们不可能每次询问都来求一边 rmq。考虑找支配点对。

对于一个支配点对 (x,y)，显然满足 \max(d_x,d_y)\le \min _{i \in (x,y)}d_i，否则 x 或 y 可以向内缩，得到更优解。

如果 d_x \le d_y，d_x 为 y 之前第一个比 d_y 小的元素。如果 d_y \le d_x，d_y 为 x 之后第一个比 d_x 小的元素。

正反分别做单调栈维护，每个点贡献 \mathcal{O}(1) 个支配对。加上点分治，一共 \mathcal{O}(n \log n) 个支配对。

扫描线，二维数点即可。时间复杂度 \mathcal{O}(n \log^2 n +q \log n)，空间复杂度 \mathcal{O}(n \log n+q)。

#include<bits/stdc++.h>
#define int long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    register int x=0,s=gc;
    while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=200005,M=1000005,inf=1e16;
bool vis[N];
int n,m,rt,sz,mx[N],siz[N],ans[M];
vector<pair<int,int> > v[N],q[N],p[N],d;
inline void chkmax(int &x,int y){x=(x<y?y:x);}
inline void chkmin(int &x,int y){x=(x>y?y:x);}
inline void find(int x,int f)
{
    siz[x]=1,mx[x]=0;
    for(auto [i,j]:v[x])
        if(i!=f&&!vis[i])find(i,x),siz[x]+=siz[i],chkmax(mx[x],siz[i]);
    chkmax(mx[x],sz-siz[x]);
    if(mx[x]<mx[rt])rt=x;
}
inline void get(int x,int l,int f)
{
    if(vis[x])return;
    d.push_back({x,l});
    for(auto [i,j]:v[x])if(i!=f)get(i,l+j,x);
}
inline void sol(int x)
{
    if(vis[x])return;
    vis[x]=1;
    for(auto [i,j]:v[x])get(i,j,x);
    d.push_back({x,0}),sort(d.begin(),d.end()); 
    stack<pair<int,int> > st;
    for(auto [i,j]:d)
    {
        while(st.size()&&st.top().second>j)st.pop();
        if(st.size())p[i].push_back({st.top().first,st.top().second+j});
        st.push({i,j});
    }
    while(st.size())st.pop();
    reverse(d.begin(),d.end());
    for(auto [i,j]:d)
    {
        while(st.size()&&st.top().second>j)st.pop();
        if(st.size())p[st.top().first].push_back({i,st.top().second+j});
        st.push({i,j});
    }
    d.clear();
    for(auto [i,j]:v[x])if(!vis[i])rt=0,sz=siz[i],find(i,x),sol(rt);    
}
struct BIT
{
    int c[N];
    inline void chk(int x,int y){while(x)chkmin(c[x],y),x^=(x&-x);}
    inline int ask(int x){int s=LONG_LONG_MAX;while(x<=n)chkmin(s,c[x]),x+=(x&-x);return s;}
}G;
signed main()
{
    n=rd;for(int i=1,x,y,w;i<n;v[x].push_back({y,w}),v[y].push_back({x,w}),++i)x=rd,y=rd,w=rd;
    m=rd;for(int i=1,l;i<=m;++i)l=rd,q[rd].push_back({l,i});
    mx[0]=n+1,rt=0,sz=n,find(1,0),sol(rt),memset(G.c,0x3f,sizeof(G.c));
    for(int i=1;i<=n;++i)
    {
        for(auto [l,k]:p[i])G.chk(l,k);
        for(auto [l,id]:q[i])ans[id]=G.ask(l);
    }
    for(int i=1;i<=m;++i)cout<<(ans[i]>inf?-1:ans[i])<<'\n';
    return 0;
}