跟隔壁的雨天的尾巴异常相似

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1.Analysis

某条路线对当前节点x有贡献时只可能是

x在s到t的路线上（即s到lca到t）

 

那么首先我们可以对从s到t的路线划分为

从s到lca(s,t)

以及从t到lca

a.from s to lca

要有贡献

易得dep[s]-dep[x]=val[x](出现时间)

观察可得寻找s满足dep[s]=dep[x]+val[x]的数量

b.from lca to t

要有贡献

易得dep[s]+dep[x]-dep[lca]-dep[lca]=val[x](出现时间)

观察可得寻找s满足dep[s]-dep[lca]-dep[lca]=val[x]-dep[x]的数量

 

为了计算.我们规定lca被算在a部分中

2.实现

a.不断从叶子到lca累加

易联想到差分

b.由于种类不同可以开权值线段树

在递归回fa时合并线段树

 

3.问题

炸空间

4.解决

就权值线段树合并后空余节点进行一波垃圾回收

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=300005,maxz=600000,maxl=300000;int n,m,k,hd[maxn],ans[maxn],val[maxn];struct node{    int to,nt;}e[maxn<<1];inline void add(int x,int y){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;}struct solu{    //分为s,t两部分    int top,tot,cnt;    int rt[maxn*30],sum[maxn*30][2],ls[maxn*30],rs[maxn*30],first[maxn];    int rab[maxn*30];    struct ll{        int flag,op,val,nt;    }st[maxn<<2];        inline void insert(int x,int y,int z,int f)    {        st[++top]=(ll){f,z,y,first[x]};        first[x]=top;    }            inline int New()    {        int now;        if(tot)now=rab[tot--];        else now=++cnt;        ls[now]=rs[now]=sum[now][0]=sum[now][1]=0;        re now;    }    inline void Throw(int x)    {        rab[++tot]=x;    }             inline int query(int rt,int l,int r,int pos,int f)    {        if(!rt)re 0;        if(l==r)            re sum[rt][f];        int mid=(l+r)>>1;        if(pos<=mid)re query(ls[rt],l,mid,pos,f);        else re query(rs[rt],mid+1,r,pos,f);    }        inline void add(int &rt,int l,int r,int pos,int vvl,int f)    {        if(!rt) rt=New();        if(l==r)        {            if(l==299999)            f=f;                        sum[rt][f]+=vvl;            re ;        }        int mid=(l+r)>>1;        if(pos<=mid)add(ls[rt],l,mid,pos,vvl,f);        else add(rs[rt],mid+1,r,pos,vvl,f);    }        inline int merge(int x,int y,int l,int r)    {        if(!x||!y)re x+y;        if(l==r)        {            if(l==299999)            x=x;            sum[x][0]+=sum[y][0];            sum[x][1]+=sum[y][1];            Throw(y);            re x;        }                int mid=(l+r)>>1;                ls[x]=merge(ls[x],ls[y],l,mid);        rs[x]=merge(rs[x],rs[y],mid+1,r);        Throw(y);        re x;    }}T;struct Tree_lca{    int top[maxn],size[maxn],son[maxn],dep[maxn],fa[maxn];        inline void dfs(int x)    {        dep[x]=dep[fa[x]]+(size[x]=1);        for(int i=hd[x];i;i=e[i].nt)        {            int v=e[i].to;            if(v!=fa[x])            {                fa[v]=x;                dfs(v);                size[x]+=size[v];                if(size[v]>size[son[x]])son[x]=v;            }        }    }        inline void dfs2(int x,int topf)    {        top[x]=topf;        if(son[x])        {            dfs2(son[x],topf);            for(int i=hd[x];i;i=e[i].nt)            {                int v=e[i].to;                if(!top[v])                dfs2(v,v);            }        }    }        inline int Lca(int x,int y)    {        while(top[x]!=top[y])        {            if(dep[top[x]]