JZOJ 4289 Mancity

首先处理出 fi 表示 i 向上一小时最多走到什么地方。
由于边权只有 1,2，这个可以树上双指针 O(n)。

询问时，显然应当跳 fi 到一个最浅的深于 LCA 的点，然后考虑最后这一段路程是否超过 D。

然而倍增是卡不过的，考虑离线，Tarjan 求 LCA 并把询问记录在 LCA 上。
注意到可以利用 Tarjan 类似的思路，用并查集来维护这个能跳到的最浅点，而利用回溯时的更新保证不会跳到 LCA 或以上。
同时需要记录步数，这个是带权并查集基本操作（

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 5e5;
int n,d,q;
namespace EDGE
{
    int to[N + 5],pre[N + 5],first[N + 5];
    inline void add(int u,int v)
    {
        static int tot = 0;
        to[++tot] = v,pre[tot] = first[u],first[u] = tot;
    }
}
int fa[N + 5],a[N + 5];
int f[N + 5],s[N + 5];
int ans[N + 5];
namespace QUERY
{
    int x[N + 5],y[N + 5],pre[N + 5],first[N + 5],id[N + 5];
    inline void add(int lca,int u,int v,int i)
    {
        static int tot = 0;
        x[++tot] = u,y[tot] = v,id[tot] = i,pre[tot] = first[lca],first[lca] = tot;
    }
}
namespace TAR1
{
    int to[(N << 1) + 5],pre[(N << 1) + 5],id[(N << 1) + 5],first[N + 5];
    int done[N + 5];
    inline int init()
    {
        memset(first,-1,sizeof first);
        return 0;
    }
    int Init = init();
    inline void add(int u,int v,int i)
    {
        static int tot = 0;
        to[tot] = v,id[tot] = i,pre[tot] = first[u],first[u] = tot++;
    }
    int fa[N + 5],vis[N + 5];
    int get(int x)
    {
        return !fa[x] ? x : (fa[x] = get(fa[x]));
    }
    void dfs(int p)
    {
        vis[p] = 1;
        for(register int i = EDGE::first[p];i;i = EDGE::pre[i])
            dfs(EDGE::to[i]),fa[EDGE::to[i]] = p;
        for(register int i = first[p];~i;i = pre[i])
            vis[to[i]] && !done[id[i]] && (QUERY::add(get(to[i]),p,to[i],id[i]),done[id[i]] = 1);
    }
}
namespace TAR2
{
    int to[N + 5],pre[N + 5],first[N + 5];
    inline void add(int u,int v)
    {
        static int tot = 0;
        to[++tot] = v,pre[tot] = first[u],first[u] = tot;
    }
    int fa[N + 5],cnt[N + 5],vis[N + 5];
    int get(int x)
    {
        if(!fa[x])
            return x;
        int f = fa[x];
        fa[x] = get(f),cnt[x] += cnt[f];
        return fa[x];
    }
    void dfs(int p)
    {
        vis[p] = 1;
        for(register int i = EDGE::first[p];i;i = EDGE::pre[i])
            dfs(EDGE::to[i]);
        for(register int i = QUERY::first[p],x,y,u,v;i;i = QUERY::pre[i])
        {
            u = get(x = QUERY::x[i]),v = get(y = QUERY::y[i]);
            ans[QUERY::id[i]] = cnt[x] + cnt[y] + (x != y) + (s[u] + s[v] - (s[p] << 1) > d);
        }
        for(register int i = first[p];i;i = pre[i])
            fa[to[i]] = p,cnt[to[i]] = 1;
    }
}
int main()
{
    freopen("mancity.in","r",stdin),freopen("mancity.out","w",stdout);
    read(n),read(d),read(q),f[1] = 1;
    for(register int i = 2;i <= n;++i)
        read(fa[i]),read(a[i]),s[i] = s[fa[i]] + a[i],f[i] = i,EDGE::add(fa[i],i);
    for(register int p = n;p;--p)
    {
        for(;fa[f[p]] && s[p] - s[fa[f[p]]] <= d;f[p] = fa[f[p]]);
        TAR2::add(f[p],p),f[fa[p]] = min(f[fa[p]],f[p]);
    }
    int u,v;
    for(register int i = 1;i <= q;++i)
        read(u),read(v),TAR1::add(u,v,i),TAR1::add(v,u,i);
    TAR1::dfs(1),TAR2::dfs(1);
    for(register int i = 1;i <= q;++i)
        printf("%d\n",ans[i]);
}