TLE#20 树链剖分求卡常

自己yy然后写的，写完T了#20,思路是树链剖分在线段树上维护等差数列，最后统计。自己算了算复杂度应该只有最坏O(nlog^2n)

code:

#include<stdio.h>
#include<list>
#include<unordered_map>
#include<ctype.h>
#include<algorithm>
#define lk k<<1
#define rk k<<1|1
#define MAXN 300000
using namespace std;
class node{
public:
int l,r,s;
unordered_map<int,int>w1,w2;
}t[MAXN<<2];
list<int>g[MAXN];
int n,m,w[MAXN],tx,ty,ans;
int tot,son[MAXN],sz[MAXN],f[MAXN],tp[MAXN],id[MAXN];
const int BUFSIZE = 1 << 24;
char ibuf[BUFSIZE], *is = ibuf, *it = ibuf;
inline char getch(){
    if(is == it)
        it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
    return is == it ? EOF : *is++;
}
inline int uread(){
    int res = 0, ch = getch();
    while(!(isdigit(ch)) and ch != EOF) ch = getch();
    while(isdigit(ch)) res = res * 10 + (ch ^ 48), ch = getch();
    return res;
}
inline void update(int k){
    t[k].s=t[lk].s+t[rk].s;
}
void dfs1(int x,int fa){
    sz[x]=1;f[x]=fa;
    for(auto it:g[x]){
        if(it==fa)continue;
        dfs1(it,x);
        sz[x]+=sz[it];
        if(sz[it]>sz[son[x]])son[x]=it;
    }
}
void dfs2(int x,int t){
    tp[x]=t;id[x]=++tot;
    if(!son[x])return;
    dfs2(son[x],t);
    for(auto it:g[x]){
        if(it==f[x] or it==son[x])continue;
        dfs2(it,it);
    }
}
//init

//tree
void build(int k,int l,int r){
    t[k].l=l,t[k].r=r;
    //printf("%d %d %d\n",k,t[k].l,t[k].r);
    if(l==r){
        t[k].s=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(lk,l,mid);
    build(rk,mid+1,r);
    update(k);
}
void aks(int k,int x,int y){
    //make
    if(t[k].l<=x and x<=t[k].r){
        //auto it=lower_bound(t[k].w1.begin(),t[k].w1.end(),y+(t[k].r-x));
        //if(it!=t[k].w1.end() and *it==y+(t[k].r-x))ans++;
        //printf("%d %d %d %d %d %d %d %d wow\n",k,t[k].l,t[k].r,x,y+(x-t[k].l),y+(t[k].r-x),t[k].w2[y+(x-t[k].l)],t[k].w1[y+(t[k].r-x)]);
        ans+=t[k].w1[y+(t[k].r-x)];
        ans+=t[k].w2[y+(x-t[k].l)];
    }
    if(t[k].l==t[k].r)return ;
    int mid=(t[k].l+t[k].r)>>1;
    if(x<=mid)aks(lk,x,y);
    else aks(rk,x,y);
}
void qch(int k,int l,int r,int w,int mo){
    //printf("%d %d f\n",l,r);
    if(l<=t[k].l and t[k].r<=r){
        if(mo){
            //printf("%d %d %d %d %d\n",k,t[k].l,t[k].r,w-(t[k].l-l),mo);
            t[k].w2[w-(t[k].l-l)]++;
        }
        else {
            //printf("%d %d %d %d %d\n",k,t[k].l,t[k].r,w-(r-t[k].r),mo);
            t[k].w1[w-(r-t[k].r)]++;
        }
        return ;
    }
    int mid=(t[k].l+t[k].r)>>1;
    if(l<=mid)qch(lk,l,r,w,mo);
    if(r>mid)qch(rk,l,r,w,mo);
}
int qask(int k,int l,int r){
    if(l<=t[k].l and t[k].r<=r){
        return t[k].s;
    }
    int mid=(t[k].l+t[k].r)>>1,ans=0;
    if(l<=mid)ans+=qask(lk,l,r);
    if(r>mid)ans+=qask(rk,l,r);
    return ans;
}

//pou
inline int get_ans(int x,int y){
    int tmp=0;
    while(tp[x]!=tp[y]){
        if(id[tp[x]]<id[tp[y]])swap(x,y);
        tmp+=qask(1,id[tp[x]],id[x]);
        x=f[tp[x]];
    }
    if(id[x]<id[y])swap(x,y);
    tmp+=qask(1,id[y],id[x]);
    return tmp;
}
inline void ch_ans(int x,int y){
    int l=-1,r=get_ans(x,y);
    //printf("%d %d %d %d %d %d %d df\n",x,y,tp[x],tp[y],id[x],id[y],r);
    while(tp[x]!=tp[y]){
        if(id[tp[x]]>id[tp[y]]){
            qch(1,id[tp[x]],id[x],l+(id[x]-id[tp[x]]+1),1);
            l+=(id[x]-id[tp[x]]+1);x=f[tp[x]];
        }
        else{
            qch(1,id[tp[y]],id[y],r-1,0);
            r-=(id[y]-id[tp[y]]+1);y=f[tp[y]];
        }
    }
    if(id[x]<=id[y]){
        //printf("%d\n",r);
        qch(1,id[x],id[y],r-1,0);
    }
    else{
        qch(1,id[y],id[x],l+(id[x]-id[y]+1),1);
    }
}
int main(){
    //freopen("P1600_20.in","r",stdin);
    //freopen("P1600.out","w",stdout);
    n=uread();m=uread();
    for(int i=1;i<n;i++){
        tx=uread();ty=uread();
        g[tx].push_back(ty);
        g[ty].push_back(tx);
    }
    for(int i=1;i<=n;i++){
        w[i]=uread();
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    //for(int i=1;i<=n;i++)printf("%d ",tp[i]);
    //puts("F");
    for(int i=1;i<=m;i++){
        tx=uread();ty=uread();
        ch_ans(tx,ty);
    }
    for(int i=1;i<=n;i++){
        ans=0;
        aks(1,id[i],w[i]);
        printf("%d ",ans);
    }
    return 0;
}