虚树第一题

对于询问多，但是询问涉及的总点数少的题型考虑建一棵虚树。

懒得讲解题目

dtoj过了，洛谷T了不管了

以下代码：

#include
      
       #define il inline#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=3e5+5;int n,head[N],ne[N<<1],to[N<<1],cnt,id[N],d[N],tot,fa[N][20];int sz[N],m,a[N],b[N],q[N],c[N],rem[N],dfn,bel[N],f[N];il int read(){
    int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;}il void insert(int x,int y){ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}bool cmp(int t1,int t2){
    return id[t1]
       
        =0;i--)if(d[fa[x][i]]>=d[y])x=fa[x][i];    if(x==y)return x;    for(int i=18;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];    return fa[x][0];}il int dis(int x,int y){
    return d[x]+d[y]-2*d[Lca(x,y)];}il void dfs1(int x){    c[++dfn]=x;rem[x]=sz[x];    for(int i=head[x];i;i=ne[i]){        dfs1(to[i]);        if(!bel[to[i]])continue;        int t1=dis(bel[to[i]],x),t2=dis(bel[x],x);        if(t1
        
         
          =0;i--)        if(d[fa[x][i]]>d[a])x=fa[x][i];    rem[a]-=sz[x];    if(bel[a]==bel[b]){        f[bel[a]]+=sz[x]-sz[b];return;    }    for(int i=18;i>=0;i--){        int nxt=fa[mid][i];        int t1=dis(bel[a],nxt),t2=dis(bel[b],nxt);        if(t1>t2||(t1==t2&&bel[b]
          
           0){            lca=Lca(t,q[tot]);            if(tot>1&&d[q[tot-1]]>d[lca])insert(q[tot-1],q[tot]),tot--;            else if(d[q[tot]]>d[lca]){insert(lca,q[tot--]);break;}            else break;        }        if(lca!=q[tot])q[++tot]=lca;q[++tot]=t;    }    while(tot>1)insert(q[tot-1],q[tot]),tot--;    dfs1(1);dfs2(1);    for(int i=1;i<=dfn;i++)        for(int j=head[c[i]];j;j=ne[j])solve(c[i],to[j]);    for(int i=1;i<=dfn;i++)f[bel[c[i]]]+=rem[c[i]];    for(int i=1;i<=m;i++)printf("%d ",f[b[i]]);puts("");    for(int i=1;i<=dfn;i++)        f[c[i]]=bel[c[i]]=head[c[i]]=0;}int main(){    n=read();    for(int i=1;i