P1600

Aryper · 2021-08-19 12:31:15 · 个人记录

[NOIP2016 提高组] 天天爱跑步

思维题，罢。

首先是，我们要枚举每个观察员，统计其它玩家对他的贡献。

然后枚举的过程是搜索子树的过程。

统计需要知道，什么样的起点或终点可以对这个观察员作贡献。

设观察员为点 p。

若起点为 s，则若 s 满足 dt_s=w_p+dt_p，且 p 在 lca(s,t)\rightarrow s 的路径上时，它能为 p 作贡献。

若起点为 t，则若 t 满足 dis_{s\rightarrow t}-w_p=dt_t-dt_p，即 dis_{s\rightarrow t}-dt_t=w_p-dt_p，且 p 在 lca(s,t)\rightarrow t 的路径上时，它能为 p 作贡献。

那么我们可以用两个桶，分别记录一个点作为起点或终点会给什么特征的点做贡献。

因为统计时要求 p 一定在 s\rightarrow t 的路径上，所以回溯的时候，要把桶内以 p 作为 lca 的贡献悉数删去。

同时，因为存在某些玩家的终点即为 lca(s,t)，并且终点恰能观察到这个玩家，按上面的方法会按照起点和终点重复统计这个玩家，我们要针对这个玩家减少一次统计。

另外，dis_{s\rightarrow t}-dt_t 与 w_p-dt_p 有着溢出的风险，需要加上一个基数。

时间复杂度 O(m\log n)。

据说还有用树剖、线段树、树状数组等维护的方法。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;

const ll N=3e5,M=3e5;

ll n,m,u,v,tot;

ll s[M+5],t[M+5],w[N+5];

ll ver[N*2+5],nxt[N*2+5],head[N+5];

ll dt[N+5],fa[N+5][30],lg[N+5];

ll b1[N*2+5],b2[N*2+5],ans[N+5],flgs[N+5],dis[N+5];

vector<ll> flglca[N+5],flgt[N+5];

void dfs(ll p,ll fath) {
    dt[p]=dt[fath]+1;fa[p][0]=fath;
    for(ll i=1;i<=lg[dt[p]];i++) {
        fa[p][i]=fa[fa[p][i-1]][i-1];
    }
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==fath) continue;
        dfs(ver[i],p);
    }
}

ll lca(ll a,ll b) {
    if(dt[a]<dt[b]) swap(a,b);
    while(dt[a]>dt[b]) a=fa[a][lg[dt[a]-dt[b]]-1];
    if(a==b) return a;
    for(ll k=lg[dt[a]]-1;k>=0;k--) {
        if(fa[a][k]!=fa[b][k]) {
            a=fa[a][k];b=fa[b][k];
        }
    }
    return fa[a][0];
}

void _dfs(ll p) {
    ll t1=b1[w[p]+dt[p]],t2=b2[w[p]-dt[p]+N];
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==fa[p][0]) continue;
        _dfs(ver[i]);
    }
    b1[dt[p]]+=flgs[p];
    for(ll i=0;i<flgt[p].size();i++) {
        b2[dis[flgt[p][i]]-dt[t[flgt[p][i]]]+N]++;
    }
    ans[p]+=b1[w[p]+dt[p]]-t1+b2[w[p]-dt[p]+N]-t2;
    for(ll i=0;i<flglca[p].size();i++) {
        b1[dt[s[flglca[p][i]]]]--;
        b2[dis[flglca[p][i]]-dt[t[flglca[p][i]]]+N]--;
    }
}

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();

    for(ll i=1;i<n;i++) {
        u=read();v=read();
        add(u,v);add(v,u);
    }

    for(ll i=1;i<=n;i++) {
        w[i]=read();
    }

    for(ll i=1;i<=n;i++) {
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }

    dfs(1,0);

    for(ll i=1;i<=m;i++) {
        s[i]=read();t[i]=read();
        ll tmp_lca=lca(s[i],t[i]);
        dis[i]=dt[s[i]]+dt[t[i]]-2*dt[tmp_lca];
        flgs[s[i]]++;
        flgt[t[i]].push_back(i);
        flglca[tmp_lca].push_back(i);
        if(dt[tmp_lca]+w[tmp_lca]==dt[s[i]]) ans[tmp_lca]--;
    }

    _dfs(1);

    for(ll i=1;i<=n;i++) {
        write(ans[i]);putchar(' ');
    }

    return 0;
}