zcmimi's blog
查看原题

点击跳转

题意:

给出一棵n个点的树,每次询问给出两对叶子,求这两对叶子产生路径的交点数

解法:

先把一条链上的点都+1,然后查询另一条链的权值和就是答案

也就是链加、链查询

可以直接树剖套线段树/树状数组 \log^2

更优秀的线性做法: 虚树

#include<bits/stdc++.h>
const int N=100011;
int n,q,cnt,head[N];
struct edge{int to,nxt;}e[N<<1];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
int siz[N],f[N],d[N],top[N],id[N],sz;
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
void dfs(int x){
    siz[x]=1;
    fl(i,x)if(to!=f[x]){
        f[to]=x;d[to]=d[x]+1;
        dfs(to);siz[x]+=siz[to];
    }
}
void bt(int x,int tp){
    top[x]=tp;id[x]=++sz;
    int k=0;
    fl(i,x)if(to!=f[x]&&siz[to]>siz[k])k=to;
    if(!k)return;bt(k,tp);
    fl(i,x)if(!top[to])bt(to,to);
}
struct bitseg{
    int s[N];int S[N];
    void upd(int x,int v){
        int V=x*v;
        if(x)for(int i=x;i<=n;i+=i&-i)
            s[i]+=v,S[i]+=V;
    }
    int ask(int x){
        int res=0;
        for(int i=x++;i;i-=i&-i)
            res+=x*s[i]-S[i];
        return res;
    }
    void upd(int l,int r,int v){upd(l,v),upd(r+1,-v);}
    int ask(int l,int r){return ask(r)-ask(l-1);}
}T;
void swap(int&x,int&y){int t=x;x=y;y=t;}
void upd(int x,int y,int v){
    while(top[x]^top[y]){
        if(d[top[x]]<d[top[y]])swap(x,y);
        T.upd(id[top[x]],id[x],v);x=f[top[x]];
    }
    if(d[x]>d[y])swap(x,y);
    T.upd(id[x],id[y],v);
}
int ask(int x,int y){
    int res=0;
    while(top[x]^top[y]){
        if(d[top[x]]<d[top[y]])swap(x,y);
        res+=T.ask(id[top[x]],id[x]);x=f[top[x]];
    }
    if(d[x]>d[y])swap(x,y);
    return res+T.ask(id[x],id[y]);
}
int main(){
    scanf("%d%d",&n,&q);
    int x,y,X,Y;
    for(int i=1;i<n;++i)
        scanf("%d%d",&x,&y),
        add(x,y),add(y,x);
    dfs(1);bt(1,1);
    while(q--){
        scanf("%d%d%d%d",&x,&y,&X,&Y);
        upd(x,y,1);
        printf("%d\n",ask(X,Y));
        upd(x,y,-1);
    }
}
GYM 101908L Subway Lines
comment评论
Search
search