天天爱跑步[NOIP2016-Day1-T2](树上差分+桶)

题目

Luogu
题目大意
一棵树，$n$ 个节点，每个点有观察员， 观察员 $i$ 在 $w_i$ 观察一次，有 $m$ 个人跑步，第 $i$ 个人从 $s_i$ 到 $t_i$ ，到达后下一秒消失， $m$ 个人同时出发，边长均为 $1$，问每个观察员观察的人数？
$1\le n,m\le 3?10^5$

思路

看着表来打

$25opt:$
考虑一些比较暴力的做法
预处理出每个人走的路径然后一秒一秒走，观察员按照时间排序，被观察到暴力加++
时间复杂度 $O(n(n+m))$

$6?20$ 发现暴力++的方法已经不行了，这就提示我们要用一些比较快的加法
差分，前缀和，线段树

$15opt:$ 链
$6?8$ 我们可以这样做
在所有 $s_i$ 处分往左右走++
把跑步的人看作 $(t_i?s_i+1，s_i,l|r)$ 的修改点
观察者看作 $(w_i,i,0)$ 的询问点
两个弄在一起按时间排序，依次处理
跑步的人拿出来后再对应桶里面–
询问的人答案贡献就是 $L[i?w_i]+R[i+w_i]$

$20opt:$ 所有 $s_i=1$
考虑 $w_i$ 会有答案当且仅当 $w_i=de{p}_i$
将跑步人的 $t_i$ 处++
然后对于 $w_i=de{p}_i$ 答案为子树和

$20opt:$ 所有 $t_i=1$
模仿 $s_i=1$ 的思路，假设第 $i$ 个人跑步时间为 $l_i=de{p}_{s_i}$ 发现 $w_i+de{p}_i=l_j$
时候会对答案产生贡献
发现这里 $w_i+de{p}_i$ 为定值
联系链的情况，想到了用桶完成操作
访问一个点记录 $b[w_i+de{p}_i]$
更新时将人挂到对应 $s_i$ 上面 然后 $b[l_i]++$
子树 DFS 完出来后 $b[w_i+de{p}_i]$ 的增量就是答案

最后 $20opt:$ 正解
上一种情况给了我们很大的启发
将一个人走的路径拆为向上走和向下走， $<s_i,lc{a}_i>$ 和 $<sonlc{a}_i,t_i>$
这里 $sonlc{a}_i$ 指包含 $t_i$ 的那个儿子

对于向上走发现对答案贡献只有当 $w_i+de{p}_i=de{p}_{s_i}$ 成立
对于向下走发现对答案贡献只有当 $w_i=l_i?(de{p}_{t_i}?de{p}_i)$ 成立，
变形可得 $w_i?de{p}_i=l_i?de{p}_{t_i}$
可以模仿链建立两种不同的询问方式
然后是点差的常规操作
在 $s_i$ 挂对应 $de{p}_{s_i}$ 加 $flca$ 挂对应 $de{p}_{s_i}$ 减
在 $t_i$ 挂对应 $l_i?de{p}_{t_i}$ 加 $lca$ 挂对应 $l_i?de{p}_{t_i}$ 减
DFS遍历完子树后统计即可

代码

#include<set>
#include<map>
#include<cmath>
#include<deque>
#include<stack>
#include<ctime>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
using namespace std;
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return f*x;
}
#define MAXN 300000
#define INF 0x3f3f3f3f
struct Edge{
    int v,nxt;
}edge[2*MAXN+5];
int ecnt,head[MAXN+5];
inline void Addedge(int u,int v){
    edge[++ecnt]=(Edge){
    v,head[u]},head[u]=ecnt;edge[++ecnt]=(Edge){
    u,head[v]},head[v]=ecnt;return ;
}
int n,m,lg2,dep[MAXN+5],fa[MAXN+5][20];
int w[MAXN+5],s[MAXN+5],t[MAXN+5];
void dfs(int u){
    for(int i=head[u];i;i=edge[i].nxt){
    int v=edge[i].v;if(v==fa[u][0]) continue;fa[v][0]=u,dep[v]=dep[u]+1,dfs(v);}return ;
}
void Prepare(){
    for(int j=1;(1<<j)<=n;j++)for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];return ;
}
int Lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);int d=dep[u]-dep[v];for(int j=lg2;j>=0;j--)if(d&(1<<j))u=fa[u][j];if(u==v)return u;for(int j=lg2;j>=0;j--)if(fa[u][j]!=fa[v][j])u=fa[u][j],v=fa[v][j];return fa[u][0];
}
vector<int> Add1[MAXN+5],Sub1[MAXN+5],Add2[MAXN+5],Sub2[MAXN+5];
int c1[2*MAXN+5],c2[2*MAXN+5],ans[MAXN+5];
void Cal(int u,int fa){
    int tmp1=c1[dep[u]+w[u]],tmp2=c2[w[u]-dep[u]+n];for(int i=head[u];i;i=edge[i].nxt){
    int v=edge[i].v;if(v==fa) continue;Cal(v,u);}for(int i=0;i<int(Add1[u].size());i++) c1[Add1[u][i]]++;for(int i=0;i<int(Sub1[u].size());i++) c1[Sub1[u][i]]--;for(int i=0;i<int(Add2[u].size());i++) c2[Add2[u][i]+n]++;for(int i=0;i<int(Sub2[u].size());i++) c2[Sub2[u][i]+n]--;ans[u]=c1[dep[u]+w[u]]+c2[w[u]-dep[u]+n]-tmp1-tmp2;return ;
}
int main(){
    n=read(),m=read(),lg2=(int)log2(n);for(int i=1;i<n;i++){
    int u=read(),v=read();Addedge(u,v);}for(int i=1;i<=n;i++)w[i]=read();for(int i=1;i<=m;i++)s[i]=read(),t[i]=read();dfs(1);Prepare();for(int i=1;i<=m;i++){
    int lca=Lca(s[i],t[i]);Add1[s[i]].push_back(dep[s[i]]);Sub1[fa[lca][0]].push_back(dep[s[i]]);int Len=dep[s[i]]+dep[t[i]]-2*dep[lca];Add2[t[i]].push_back(Len-dep[t[i]]);Sub2[lca].push_back(Len-dep[t[i]]);}Cal(1,0);for(int i=1;i<=n;i++)printf("%d",ans[i]),putchar(i==n?'\n':' ');return 0;
}