accoders NOI #5014. 树上询问(query) 题解

昨天刚刚做过一道类似的题，没想到在模拟赛当中出现了。

题目描述

有一棵 \(n\) 个结点的树，有 \(m\) 次询问，每次询问给你两个整数 \(l,r\)，问存在多少个整数 \(k\) 使得从 \(l\) 沿着 \(l\) 到 \(r\) 的简单路径走 \(k\) 步恰好到达 \(k\)。

思路

考虑将一条 \(l\) 到 \(r\) 的路径拆成 \(l\) 到 \(lca\) 和 \(lca\) 到 \(r\)。

设 \(dep_x\) 表示结点 \(x\) 的深度，\(l\) 到 \(lca\) 的贡献就是 \(\sum_{x\in[l,lca]}[dep_l-dep_x=x]=\sum_{x\in[l,lca]}[dep_l=x+dep_x]\)，\(lca\) 到 \(r\) 的答案是 \(\sum_{y\in[lca,r]}[dep_r-dep_y=len-y]=\sum_{y\in[lca,r]}[dep_r-len=dep_y-y]\)

对于 \(l\) 到 \(lca\) 路径上，\(dep_l\) 为定值，那么运用树上差分的思想，可以将 \(root\) 到 \(l\) 路径上的答案减去 \(root\) 到 \(lca\) 路径上的答案得到。\(lca\) 到 \(r\) 路径上同理。

Code

/*
 * Title: 267C. 树上询问(query)
 * Source: accoders NOI-2022NOIP A层联测12
 * URL: http://47.92.197.167:5283/contest/267/problem/3
 * Author: Steven_lzx
 * Command: -std=c++14 -O2 -lm -Wall -fno-ms-extensions
 * Date: 2022.10.21
 */
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 300005
int n,m,x,y,z,l[MAXN],r[MAXN],c[MAXN],dep[MAXN],t[MAXN<<1],f[MAXN][21],pre[MAXN],suf[MAXN],tot,len,now,ans[MAXN];
int nxt[MAXN<<1],head[MAXN],to[MAXN<<1],cnt,qTo[MAXN<<1],w[MAXN<<1],qNxt[MAXN<<1],qHead[MAXN];
namespace FASTIO
{
    inline int read()
    {
        int res=0,f=1;
        char ch=getchar();
        while(!isdigit(ch))
        {
            if(ch=='-')
                f=-1;
            ch=getchar();
        }
        while(isdigit(ch))
        {
            res=res*10+ch-'0';
            ch=getchar();
        }
        return res*f;
    }
    void write(int x)
    {
        int top=0;
        char st[25];
        do 
        {
            st[++top]=x%10+'0';
            x/=10;
        }
        while(x);
        while(top)
            putchar(st[top--]);
        return;
    }
}
using namespace FASTIO;
namespace GRAPH
{
    inline void addEdge(const int &x,const int &y)
    {
        nxt[++tot]=head[x];
        head[x]=tot;
        to[tot]=y;
        return;
    }
    void DFS1(const int &u,const int &fa)
    {
        int v;
        f[u][0]=fa;
        dep[u]=dep[fa]+1;
        t[dep[u]+u]++;
        pre[u]=t[dep[u]];
        for(register int i=head[u];i;i=nxt[i])
        {
            v=to[i];
            if(v==fa)
                continue;
            DFS1(v,u);
        }
        t[dep[u]+u]--;
        return;
    }
    inline int lca(int x,int y)
    {
        if(dep[x]<dep[y])
            swap(x,y);
        for(register int i=19;~i;i--)
            if(dep[f[x][i]]>=dep[y])
                x=f[x][i];
        if(x==y)
            return x;
        for(register int i=19;~i;i--)
        {
            if(f[x][i]!=f[y][i])
            {
                x=f[x][i];
                y=f[y][i];
            }
        }
        return f[x][0];
    }
    void insEdge(int x,int id,int len)
    {
        qNxt[++cnt]=qHead[x];
        qHead[x]=cnt;
        qTo[cnt]=id;
        w[cnt]=len;
        return;
    }
    void DFS2(int x,int y,int op)
    {
        (op)?t[dep[x]+x]++:t[dep[x]-x+n]++;
        for(register int i=qHead[x];i;i=qNxt[i])
        {
            now=((op)?t[w[i]]:t[dep[r[qTo[i]>m?qTo[i]-m:qTo[i]]]-w[i]+n]);
            if(qTo[i]>m)
                ans[qTo[i]-m]-=now;
            else
                ans[qTo[i]]+=now;
        }
        for(register int i=head[x];i;i=nxt[i])
            if(to[i]!=y)
                DFS2(to[i],x,op);
        (op)?t[dep[x]+x]--:t[dep[x]-x+n]--;
        return;
    }
}
using namespace GRAPH;
int main()
{
	freopen("query.in","r",stdin);
	freopen("query.out","w",stdout);
	n=read();
    m=read();
	for(register int i=1;i<n;i++)
    {
		x=read();
        y=read();
		addEdge(x,y);
        addEdge(y,x);
	}
	DFS1(1,0);
	for(register int j=1;j<=19;j++)
        for(register int i=1;i<=n;i++)
            f[i][j]=f[f[i][j-1]][j-1];
	for(register int i=1;i<=m;i++)
    {
		l[i]=read();
        r[i]=read();
        c[i]=lca(l[i],r[i]);
		ans[i]=pre[l[i]];
		insEdge(r[i],i,dep[l[i]]+dep[r[i]]-2*dep[c[i]]);
		insEdge(c[i],i+m,dep[l[i]]+dep[r[i]]-2*dep[c[i]]);
	}
	DFS2(1,0,0);
	cnt=0;
	memset(qHead,0,sizeof(qHead));
	for(int i=1;i<=m;i++)
        insEdge(f[c[i]][0],i+m,dep[l[i]]);
	DFS2(1,0,1);
	for(register int i=1;i<=m;i++)
    {
        write(ans[i]);
        putchar('\n');
    }
    fclose(stdin);
    fclose(stdout);
	return 0;
}

原文地址：http://www.cnblogs.com/2020gyk080/p/16813263.html