Subway Lines （树链剖分+线段树）

L. Subway Lines
time limit per test0.5 seconds
memory limit per test1024 megabytes
inputstandard input
outputstandard output
The subway system of a major city is formed by a set of stations and tunnels that connect some pairs of stations. The system was designed so that there is exactly one sequence of tunnels linking any pair of stations. The stations for which there is only one tunnel passing through are called terminals. There are several train lines that make round trips between pairs of terminal stations, passing only through the stations in the unique path between them. People are complaining about the current lines. Therefore, the mayor ordered that the lines are redefined from scratch. As the system has many stations, we need to help the engineers, who are trying to decide which pair of terminals will define a line.

The figure illustrates a system where terminal stations are shown as filled circles and the non-terminals are shown as empty circles. On the leftmost picture, if the pair $$$(A, B)$$$ define a line and the pair $$$(C, D)$$$ defines another, they won't have any common station. But, on the rightmost picture, we can see that if the pairs $$$(E, F)$$$ and $$$(G, H)$$$ are chosen, those two lines will have two stations in common.


Given the description of the system and a sequence of $$$Q$$$ queries consisting of two pairs of terminals, your program should compute, for each query, how many stations the two lines defined by those pairs have in common.

Input
The first line of the input contains two integers $$$N$$$ ($$$5 \leq N \leq 10^5$$$) and $$$Q$$$ ($$$1 \leq Q \leq 20000$$$), representing respectively the number of stations and the number of queries. The stations are numbered from 1 to $$$N$$$. Each of the following $$$N?1$$$ lines contains two distinct integers $$$U$$$ and $$$V$$$ ($$$1 \leq U, V \leq N$$$), indicating that there is a tunnel between stations $$$U$$$ and $$$V$$$. Each of the following $$$Q$$$ lines contains four distinct integers $$$A, B, C, D$$$ ($$$1 \leq A, B, C, D \leq N$$$), representing a query: the two train lines are defined by pairs $$$(A, B)$$$ and $$$(C, D)$$$.

Output
For each query, your program must print a line containing an integer representing how many stations the two train lines defined by the query would have in common.

Examples
inputCopy
5 1
1 5
2 5
5 3
5 4
1 2 3 4
outputCopy
1
inputCopy
10 4
1 4
4 5
3 4
3 2
7 3
6 7
7 8
10 8
8 9
6 10 2 5
1 9 5 10
9 10 2 1
5 10 2 9
outputCopy
0
4
0
3

思路： 树链剖分+线段树 模板题

#include 
using namespace std;
#define ri register int 
#define  M 100055

template <class G> void read(G &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
}

int n,m;
vector<int> q[M];
int vis[M],fa[M],dep[M],sz[M],son[M];
void dfs1(int a,int f)
{
    dep[a]=dep[f]+1;
    fa[a]=f;
    sz[a]++;
    vis[a]=1;
    int mx=0;
    for(ri i=0;i)
    {
        int b=q[a][i];
        if(vis[b]) continue;
        dfs1(b,a);
        sz[a]+=sz[b];
        if(sz[b]>mx)
        {
            mx=sz[b];
            son[a]=b;
        }
    }
}
int id[M],addr[M],cur,hao[M],top[M];
void dfs2(int a,int f)
{
    top[a]=f;
    vis[a]=1;
    id[a]=++cur;
    addr[cur]=a;
    
    if(son[a]) dfs2(son[a],f);
    for(ri i=0;i)
    {
        int b=q[a][i];
        if(vis[b]) continue;
        dfs2(b,b);
    }
    hao[a]=cur;
}
struct dian{
    int l,r,val;
}p[M*4];
int lz[M*4];// important
void build(int l,int r,int i)
{
    p[i].l=l;p[i].r=r;
    if(l==r)
    {
        p[i].val=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,i<<1);
    build(mid+1,r,i<<1|1);
}
void down(int i)
{
    
    lz[i<<1]+=lz[i];
    lz[i<<1|1]+=lz[i];
    p[i<<1].val+=lz[i]*(p[i<<1].r-p[i<<1].l+1);
    p[i<<1|1].val+=lz[i]*(p[i<<1|1].r-p[i<<1|1].l+1);
    lz[i]=0;
}
void xiu(int l,int r,int i,int x)
{
    if(l>p[i].r||rreturn ;
    if(l<=p[i].l&&p[i].r<=r)
    {
        p[i].val+=x*(p[i].r-p[i].l+1);
        lz[i]+=x;
        return ;
    }
    if(lz[i]) down(i);
    xiu(l,r,i<<1,x);
    xiu(l,r,i<<1|1,x);
    p[i].val=p[i<<1].val+p[i<<1|1].val;
}

void lca(int a,int b)
{
    while(top[a]!=top[b])
    {
        if(dep[top[a]]<dep[top[b]]) swap(a,b);
        xiu(id[top[a]],id[a],1,1);
        a=fa[top[a]];
    }
    if(dep[a]<dep[b]) swap(a,b);
    xiu(id[b],id[a],1,1);
}
void s_lca(int a,int b)
{
    while(top[a]!=top[b])
    {
        if(dep[top[a]]<dep[top[b]]) swap(a,b);
        xiu(id[top[a]],id[a],1,-1);
        a=fa[top[a]];
    }
    if(dep[a]<dep[b]) swap(a,b);
    xiu(id[b],id[a],1,-1);
}
int qu(int l,int r,int i)
{
    if(l>p[i].r||rreturn 0;
    if(l<=p[i].l&&p[i].r<=r)
    {
        return p[i].val;
    }
    if(lz[i]) down(i);
    return qu(l,r,i<<1)+qu(l,r,i<<1|1);
}
void q_lca(int a,int b)
{
    long long ans=0;
    while(top[a]!=top[b])
    {
        if(dep[top[a]]<dep[top[b]]) swap(a,b);
        ans+=qu(id[top[a]],id[a],1);
        a=fa[top[a]];
    }
    if(dep[a]<dep[b]) swap(a,b);
    ans+=qu(id[b],id[a],1);
    printf("%lld\n",ans);
}
int main(){
    
    read(n);read(m);
    for(ri i=1;i)
    {
        int a,b;
        read(a);read(b);
        q[a].push_back(b);
        q[b].push_back(a);
    }
    dfs1(1,1);
    memset(vis,0,sizeof(vis));
    dfs2(1,1);
    
    build(1,n,1);
    for(ri i=1;i<=m;i++)
    {
        int a,b,c,d;
        read(a);read(b);read(c);read(d);
        lca(a,b);
        q_lca(c,d);
        s_lca(a,b);
    }
    return 0;
} 

后记：

• 特别注意整么建树，
• lazy的使用，尽量用之前已经有的模板，自己想出一个新的可能出错，
• 开的范围一定是4倍，lz也是这样。
• 树链剖分的线段树： build的时候树根是 val 【addr【l】】，不要搞错了
• 都是用id。

 线段树：

    注意建树的那几个，和 lazy的向下传递，修改时的更新，和在区间内的return

void build(int l,int r,int i)
{
    p[i].l=l;p[i].r=r;
    if(l==r)
    {
        p[i].val=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,i<<1);
    build(mid+1,r,i<<1|1);
}