智乃的点分树（模板）

C++(g++ 7.5.0) 解法, 执行用时: 675ms, 内存消耗: 71796K, 提交时间: 2022-09-21 19:38:29

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

using namespace std ;

using ll = long long ;
using pii = pair<int,int> ;

const int N = 4e5 + 100 , M = 2 * N ;

int n,m ;
int h[N],e[M],ne[M],idx ;
int sz[N] ;
struct Ponit{
    int gr,dist,di ;
};
vector<Ponit> po[N] ;
struct Son{
    vector<vector<int>> son ;
    vector<int> all ;
};
Son ji[N] ;
bool st[N] ;

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++ ;
}

int getsz(int u,int fa){
    int tot = 1 ;
    for(int i = h[u] ; ~ i ; i = ne[i]){
        int j = e[i] ;
        if(j == fa || st[j]) continue ;
        tot += getsz(j,u) ;
    }
    return tot ;
}

int getgravity(int u,int fa,int sum){
    int gr = -1,mx = 0 ;
    sz[u] = 1 ;
    for(int i = h[u] ; ~ i ; i = ne[i]){
        int j = e[i] ;
        if(j == fa || st[j]) continue ;
        int nx = getgravity(j,u,sum) ;
        if(nx != -1) gr = nx ;
        sz[u] += sz[j] ;
        mx = max(mx,sz[j]) ;
    }
    mx = max(mx,sum - sz[u]) ;
    if(2 * mx <= sum) gr = u ;
    return gr ;
}

void dfs(int u,int fa,int gr,int di,int dist){
    po[u].push_back({gr,dist,di}) ;
    ji[gr].son[di].push_back(dist) ;
    ji[gr].all.push_back(dist) ;
    for(int i =  h[u] ; ~ i ; i = ne[i]){
        int j = e[i] ;
        if(j == fa || st[j]) continue ;
        dfs(j,u,gr,di,dist+1) ;
    }
}

void divtree(int u){
    int tot = getsz(u,-1) ;
    int gr = getgravity(u,-1,tot) ;
    st[gr] = 1 ;

    // 进行处理所有的东西
    po[gr].push_back({gr,0,-1}) ;
    ji[gr].all.push_back(0) ;
    int son_id = 0 ;
    for(int i = h[gr] ; ~ i ; i = ne[i]){
        int j = e[i] ;
        if(st[j]) continue ;
        ji[gr].son.push_back({}) ;
        dfs(j,gr,gr,son_id,1) ;
        son_id ++ ;
    }

    for(int i = h[gr] ; ~ i ; i = ne[i]){
        int j = e[i] ;
        if(st[j]) continue ;
        divtree(j) ;
    }
}

int calc(vector<int> &v,int d){
    if(v.empty()) return 0 ;
    if(v.back() <= d) return v.size() ;
    return upper_bound(v.begin(), v.end(),d) - v.begin() ;
}

int query(int u,int d){
    int ans = 0 ;
    for(Ponit t : po[u]){
        int gr = t.gr ;
        int dist = t.dist ;
        int di = t.di ;
        if(dist > d) continue ;
        ans += calc(ji[gr].all,d-dist);
        if(di != -1) ans -= calc(ji[gr].son[di],d-dist) ;
    }
    return ans ;
}

int main(){
    scanf("%d%d",&n,&m) ;
    memset(h,-1,sizeof h) ;
    for(int i = 1 ; i <= n - 1 ; i ++){
        int a,b ;
        scanf("%d%d",&a,&b) ;
        add(a,b),add(b,a) ;
    }
    divtree(1) ;
    for(int x = 1 ; x <= n ; x ++){
        sort(ji[x].all.begin(), ji[x].all.end()) ;
        for(vector<int> &v : ji[x].son)
            sort(v.begin(), v.end()) ;
    }

    int ans = 0 ;
    for(int i = 1 ; i <= m ; i ++){
        int u,d ;
        scanf("%d%d",&u,&d) ;
        u = (ans + u) % n + 1 ;
        ans = query(u,d) ;
        printf("%d\n",ans) ;
    }
    return 0 ;
}

C++ 解法, 执行用时: 906ms, 内存消耗: 50296K, 提交时间: 2022-05-12 20:27:33

#include<bits/stdc++.h>
#define pw(a) (1LL<<(a))
#define L ((p)<<1)
#define R ((p)<<1|1)
#define endl '\n'
using namespace std;
 
typedef long long LL;
typedef double DD;
typedef pair<int,int> PR;
 
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int N=1e5+10;
 
int n,m,k,t;
int st[N+N][20],f[N],dep[N],id[N],idx=0;

vector<int>adj[N];
struct BIT
{
	int n;
	vector<int>tre;
	void init(int x)
	{
		n=x+5;
		tre.resize(n+5);
	}
	void update(int x)
	{
		x++;
		for(int i=x;i<=n;i+=i&-i) tre[i]++;
	}
	int query(int x)
	{
		x++;
		int res=0;
		for(int i=min(n,x);i>=1;i-=i&-i) res+=tre[i];
		return res;
	}
}P[N],F[N];
void dfs(int u,int p)
{
	dep[u]=dep[p]+1;
	st[++idx][0]=u;
	id[u]=idx;
	for(int x:adj[u])
	{
		if(x==p) continue;
		dfs(x,u);
		st[++idx][0]=u;
	}
}
int minv(int x,int y)
{
	if(dep[x]<dep[y]) return x;
	return y;
}
int getdis(int x,int y)
{
	int l=id[x],r=id[y];
	if(l>r) swap(l,r);
	int k=log2(r-l+1);
	int lca=minv(st[l][k],st[r-pw(k)+1][k]);
	return dep[x]+dep[y]-dep[lca]-dep[lca];
}
int vis[N];

int getsz(int u,int p)
{
	int sz=1;
	for(int x:adj[u])
	{
		if(vis[x]||x==p) continue;
		sz+=getsz(x,u);
	}
	return sz;
}
int getwc(int u,int p,int tot,int &wc)
{
	int ms=0,sz=1;
	for(int x:adj[u])
	{
		if(vis[x]||x==p) continue;
		int t=getwc(x,u,tot,wc);
		sz+=t;
		ms=max(ms,t);
	}
	ms=max(ms,tot-sz);
	if(ms<=tot/2) wc=u;
	return sz;
}
void acd(int u,int p)
{
	int tot=getsz(u,0);
	getwc(u,0,tot,u);
	F[u].init(tot);
	P[u].init(tot);
	vis[u]=1;
	f[u]=p;
	for(int x:adj[u])
	{
		if(not vis[x]) acd(x,u);
	}
}

void update(int x)
{
	for(int i=x;i;i=f[i]) P[i].update(getdis(x,i));
	for(int i=x;f[i];i=f[i]) F[i].update(getdis(x,f[i]));
}
int query(int x,int d)
{
	int res=P[x].query(d);
	for(int i=x;f[i];i=f[i])
	{
		int dis=getdis(x,f[i]);
		if(dis<=d) res+=P[f[i]].query(d-dis)-F[i].query(d-dis);
	} 
	return res;
}
#undef L
#undef R
signed main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1,x,y;i<n;i++)
	{
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	dfs(1,0);
	acd(1,0);
	for(int j=1;j<=18;j++)
	for(int i=1;i+pw(j-1)<=n+n;i++) st[i][j]=minv(st[i][j-1],st[i+pw(j-1)][j-1]);
	for(int i=1;i<=n;i++) update(i);
	int ans=0;
	while(m--)
	{
		int x,d;
		cin>>x>>d;
		x=(x+ans)%n+1;
		ans=query(x,d);
		cout<<ans<<endl;
	}
	return 0;
}

详情