原发布时间：2023/07/18 22:14

天天爱跑步 | P1600

题目是GPT取的

天天

爱

跑步

这道题告诉我们，要熟练掌握STL容器的理解与应用

《关于map容器的实践与应用》

别学我这个不会打树状数组的sb

#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <bits/basic_string.h>
#include <map>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
int n,m;
const int MAXN=3e5+5;
inline int read(){
    int s=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0' && c<='9')s=s*10+c-'0',c=getchar();
    return s*f;
}
int head[MAXN];
struct tree{
    int to,next;
}edge[MAXN*2];
int cnt=0;
void add(int u,int v){
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int c[MAXN];
int query(int x){int ret=0;for(int i=x;;i-=lowbit(i)){ret+=c[i];if(i==0)break;}return ret;}
void modify(int x,int v){if(x==0)return;for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;}
int obs[MAXN];
int d[MAXN][20];
int dfn[MAXN];
int depth[MAXN];
int ma[MAXN];
int cnt2=0;
void dfs(int r,int dep){
    dfn[r]=++cnt2;
    depth[r]=dep;
    ma[r]=dfn[r];
    for(int i=head[r];i!=-1;i=edge[i].next){
        int s=edge[i].to;
        if(dfn[s])continue;
        d[s][0]=r;
        for(int i=1;i<20;i++){
            d[s][i]=d[d[s][i-1]][i-1];
        }  
        dfs(s,dep+1);
        ma[r]=max(ma[r],ma[s]);
    }
}
int LCA(int x,int y){
    if(depth[x]<depth[y])swap(x,y);
    while(depth[x]!=depth[y]){
        for(int i=19;i>=0;i--){
            if(depth[d[x][i]]>=depth[y]){
                x=d[x][i];
            }
        }
    }
    if(x==y)return x;
    for(int i=19;i>=0;i--){
        if(d[x][i]!=d[y][i]){
            x=d[x][i];
            y=d[y][i];
        }
    }
    return d[x][0];
}                        
map<int,basic_string< pair<int,int> > >up;
map<int,basic_string< pair<int,int> > >down;
map<int,basic_string< int > >upo;
map<int,basic_string< int > >downo;
int ans[MAXN];
signed main(){
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    int _u,_v;
    for(int i=1;i<n;i++){
        _u=read(),_v=read();
        add(_u,_v);
        add(_v,_u);       
    }
    dfs(1,1);
    for(int i=1;i<=n;i++){
        obs[i]=read();
        upo[depth[i]+obs[i]]+=i;
        downo[obs[i]-depth[i]]+=i;
    }
    for(int i=1;i<=m;i++){
        _u=read(),_v=read();
        int lca=LCA(_u,_v);
        if(lca==_v){
            up[depth[_u]]+=(pair<int,int>){_u,d[lca][0]};    
        }
        else if(lca==_u){
            down[depth[_u]-2*depth[_u]]+=(pair<int,int>){_v,d[_u][0]};
        }
        else{
            up[depth[_u]]+=(pair<int,int>){_u,d[lca][0]};
            down[depth[_u]-2*depth[lca]]+=(pair<int,int>){_v,lca};
        }
    }
    for(auto i:up){
        for(auto j:i.second){
            modify(dfn[j.first],1);
            modify(dfn[j.second],-1);
        }
        for(auto j:upo[i.first])ans[j]+=query(ma[j])-query(dfn[j]-1);
        for(auto j:i.second){
            modify(dfn[j.first],-1);
            modify(dfn[j.second],1);
        }
    }
    for(auto i:down){
        for(auto j:i.second){
            modify(dfn[j.first],1);
            modify(dfn[j.second],-1);
        }
        for(auto j:downo[i.first])
            ans[j]+=query(ma[j])-query(dfn[j]-1);
        for(auto j:i.second){
            modify(dfn[j.first],-1);
            modify(dfn[j.second],1);
        }
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    return 0;
}