[Noip 2016] 매일 달리기 (나무 사슬 분할)

전송 문 은 문화 수업 을 시작 하고 문 제 를 쓰 는 시간 이 너무 적다 고 합 니 다.이 문 제 는 한 사람의 달리기 노선 을 s - > lca, lca - > t 로 나 눈 다음 에 첫 번 째 오르막 경 로 를 거 쳐 야 하 는 점 에 대해 현재 이 사람 이 기여 할 수 있 고 dep [s] - dep [i] = w [i] 만 할 수 있 으 며 두 번 째 경로 에 똑 같이 기여 할 수 있 으 며 dep [t] - dep [i] = dis (s, t) - w [i] 만 할 수 있다. 이 동시에 lca 가 무 거 운 계산 을 받 았 는 지 봐 야 한다. 이 몇 가 지 를 보면 차이 가 난다.하지만 차이 점 은 생각 지도 쓰기 도 어 려 울 뿐만 아니 라 데이터 구조 로 대체 하 겠 습 니 다.사실은 나무 사슬 분할 + 동적 개방 점 입 니 다.코드:

#include
#define N 300005
using namespace std;
int n,m;
int hson[N],num[N],ans[N],first[N],top[N],dep[N],fa[N],siz[N],dfn=0,tot=0,cnt=0,rt[N*3];
struct Node{int l,r,sum;}T[N*30];
struct node{int v,next;}e[N<<1];
int s[N],t[N],w[N],lca[N];
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline int read(){
    int ret=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();
    return ret;
}
inline void dfs1(int p){
    siz[p]=1,hson[p]=0;
    for(int i=first[p];i;i=e[i].next){
        int v=e[i].v;
        if(v==fa[p])continue;
        fa[v]=p,dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];
        if(siz[v]>siz[hson[p]])hson[p]=v;
    }
}
inline void dfs2(int p,int tp){
    top[p]=tp,num[p]=++dfn;
    if(hson[p])dfs2(hson[p],tp);
    for(int i=first[p];i;i=e[i].next){
        int v=e[i].v;
        if(v!=hson[p]&&v!=fa[p])dfs2(v,v);
    }
}
inline void update(int&p,int l,int r,int k,int v){
    if(!p)p=++tot,T[p].l=T[p].r=T[p].sum=0;
    T[p].sum+=v;
    if(l==r)return;
    int mid=l+r>>1;
    if(k<=mid)update(T[p].l,l,mid,k,v);
    else update(T[p].r,mid+1,r,k,v);
}
inline int query(int p,int l,int r,int ql,int qr){
    if(!p)return 0;
    if(ql<=l&&r<=qr)return T[p].sum;
    int mid=l+r>>1;
    if(qr<=mid)return query(T[p].l,l,mid,ql,qr);
    if(ql>mid)return query(T[p].r,mid+1,r,ql,qr);
    return query(T[p].l,l,mid,ql,mid)+query(T[p].r,mid+1,r,mid+1,qr);
}
inline int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]return dep[x]int main(){
    n=read(),m=read();
    for(int i=1;iint u=read(),v=read();
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;++i)w[i]=read();
    dfs1(1),dfs2(1,1);
    for(int i=1;i<=m;++i){
        s[i]=read(),t[i]=read();
        lca[i]=LCA(s[i],t[i]);
        if(dep[s[i]]-dep[lca[i]]==w[lca[i]])--ans[lca[i]];
        update(rt[dep[s[i]]],1,n,num[s[i]],1);
        if(fa[lca[i]])update(rt[dep[s[i]]],1,n,num[fa[lca[i]]],-1);
    }
    for(int i=1;i<=n;++i)ans[i]+=query(rt[w[i]+dep[i]],1,n,num[i],num[i]+siz[i]-1);
    memset(rt,0,sizeof(rt)),tot=0;
    for(int i=1;i<=m;++i){
        update(rt[n*2+dep[s[i]]-2*dep[lca[i]]],1,n,num[t[i]],1);
        if(fa[lca[i]])update(rt[n*2+dep[s[i]]-2*dep[lca[i]]],1,n,num[fa[lca[i]]],-1);
    }
    for(int i=1;i<=n;++i)ans[i]+=query(rt[w[i]-dep[i]+n*2],1,n,num[i],num[i]+siz[i]-1);
    for(int i=1;i<=n;++i)cout<' ';
    return 0;
}