C++(clang++11) 解法, 执行用时: 400ms, 内存消耗: 24864K, 提交时间: 2021-02-04 21:35:04

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,bs=20001;
int n,q,tot,head[N],nex[N<<1],to[N<<1];
int id,son[N],top[N],fa[N],dep[N],len[N],dfn[N];
int L,R;
void add(int u,int v)
{
    to[++tot]=v;nex[tot]=head[u];head[u]=tot;
}
void dfs1(int u,int p)
{
    dep[u]=dep[p]+1;fa[u]=p;
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==p) continue;
        dfs1(v,u);
        len[u]=max(len[u],len[v]);
        if(len[v]>len[son[u]]) son[u]=v;
    }
    len[u]++;
}
void dfs2(int u,int tp)
{
    top[u]=tp;dfn[u]=++id;
    if(son[u]) dfs2(son[u],tp);
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(dfn[v]) continue;
        dfs2(v,v);
    }
}
int LCA(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]]) u=fa[top[u]];
        else v=fa[top[v]];
    }
    return dep[u]<dep[v]?u:v;
}
int tlca[N<<2];
void buildlca(int l,int r,int k)
{
    if(l==r)
    {
        tlca[k]=l;return;
    }
    int m=l+r>>1;
    buildlca(l,m,k<<1);buildlca(m+1,r,k<<1|1);
    tlca[k]=LCA(tlca[k<<1],tlca[k<<1|1]);
}
int querylca(int l,int r,int k,int x,int y)
{
    if(l>=x&&r<=y) return tlca[k];
    int m=l+r>>1;
    if(x<=m&&y>m) return LCA(querylca(l,m,k<<1,x,y),querylca(m+1,r,k<<1|1,x,y));
    else if(x<=m) return querylca(l,m,k<<1,x,y);
    return querylca(m+1,r,k<<1|1,x,y);
}
vector<pair<int,int>>query[N];
int ans[N],bit[N];
int qsum(int x)
{
    int ans=0;
    while(x) ans+=bit[x],x-=x&-x;
    return ans;
}
void Add(int x,int val)
{
    while(x<=n) bit[x]+=val,x+=x&-x;
}
int t[N<<2];
bool vis[N<<2];
void del(int l,int r,int k)
{
    if(!vis[k]) return;
    vis[k]=false;
    if(t[k])
    {
        Add(t[k],-(r-l+1));
        t[k]=0;
        return;
    }
    int m=l+r>>1;
    del(l,m,k<<1);del(m+1,r,k<<1|1);
}
void update(int l,int r,int k,int x,int y,int id)
{
    if(r<x||l>y) return;
    if(l>=x&&r<=y)
    {
        del(l,r,k);
        t[k]=id;vis[k]=true;
        return;
    }
    int m=l+r>>1;
    if(t[k])
        t[k<<1]=t[k<<1|1]=t[k],vis[k<<1]=vis[k<<1|1]=true,t[k]=0;
    update(l,m,k<<1,x,y,id);
    update(m+1,r,k<<1|1,x,y,id);
    vis[k]=vis[k<<1]|vis[k<<1|1];
}
void Insert(int u)
{
    int id=u;
    Add(u,dep[u]);
    while(u)
    {
        update(1,n,1,dfn[top[u]],dfn[u],id);
        u=fa[top[u]];
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs1(1,0);
    dfs2(1,1);
    buildlca(1,n,1);
    for(int i=1;i<=q;i++)
    {
        int l,r;scanf("%d%d",&l,&r);
        query[r].push_back({l,i});
    }
    for(int i=1;i<=n;i++)
    {
        Insert(i);
        for(pair<int,int>x:query[i])
            ans[x.second]=qsum(i)-qsum(x.first-1)-dep[querylca(1,n,1,x.first,i)];
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
}