[NOIP2016][思维+树上倍增]天天爱跑步

昨天做这道题大概做了两个小时才过…大概要在考场上做出来很困难罢…
不过这题目确实比平时做的那些辣鸡考试题目好多了。

题面

题目描述

小 $c$ 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线,完成打卡任务。

这个游戏的地图可以看作一一棵包含 $n$ 个结点和 $n?1$ 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 $1$ 到 $n$ 的连续正整数。

现在有 $m$ 个玩家，第 $i$ 个玩家的起点为 $s_i$，终点为 $t_i$ 。每天打卡任务开始时，所有玩家在第 $0$ 秒同时从自己的起点出发, 以每秒跑一条边的速度, 不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树, 所以每个人的路径是唯一的)

小 $c$ 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点$j$ 的观察员会选择在第 $w_j$ 秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第 $w_j$ 秒也理到达了结点 $j$ 。小 $c$ 想知道每个观察员会观察到多少人?

注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一 段时间后再被观察员观察到。 即对于把结点 $j$ 作为终点的玩家: 若他在第 $w_j$ 秒前到达终点,则在结点 $j$ 的观察员不能观察到该玩家；若他正好在第 $w_j$ 秒到达终点,则在结点 $j$ 的观察员可以观察到这个玩家。

子任务

这个很重要
每个测试点的数据规模及特点如下表所示。
提示: 数据范围的个位上的数字可以帮助判断是哪一种数据类型。

题解

针对测试点1-2

开个数组数一下$W_i=0$的答案。
复杂度：$O(n)$

针对测试点3-4

跟上一个其实没什么区别。
复杂度：$O(n)$

针对测试点1-5

考虑用DFS模拟每个人走的过程，如果这个点上的人恰好正在统计，$cnt++$即可。
复杂度$O(mn)$

针对测试点6-8

注意到一个点$i$会统计的只有起点在$i?W_i$且向右和起点在$i+W_i$且向左的人。
因此我们将向左和向右的分开统计，从$1?n$或$n?1$扫描，用$cnt[s]$统计以$s$为起点的人数，到达终点时$cnt[s]??$即可。
复杂度：$O(n)$

针对测试点9-12

只有$W_i=de{p}_i$的点才会有答案，因此一遍DFS统计子树内有多少个$t$就好了。
复杂度：$O(n)$

正解1

经过6-8测试点的提示，容易想到将一个树链拆成上行下行两条链分别考虑，对每个子树都维护一个$cnt$数组，更新信息的话我们只要将它的儿子的信息一个一个的合并上去就好了。
直接这样做显然空间会爆炸，然而如果我们用超纲的动态开点线段树合并就没有问题了。
复杂度:$O(n\log n)$

针对测试点13-16

这是整道题目最关键的一步。
如果你想的到的话你会发现可以直接用$cnt$的增量来维护当前子树内的信息。
具体来说，我们在dfs入栈时减去$cnt[查询的位置]$，出栈时加上$cnt[查询的位置]$。
对于这一部分数据，我们只用维护上行链就好了（大概这一部分是给那些不会算下行链时间的同学设计的）。
复杂度：$O(n)$

正解2

与正解1一样，我们拆成两条链分别考虑，但现在我们只需要用一个$cnt$数组就能够统计了。
接下来我们重点谈谈怎么算查询的位置的问题（就这个地方我卡了半天…）。
1.对于上行路径，比较简单，我们只需要想像查询的是当前点子树的$W_i$级儿子就好了。
因此插入$dep[s]$，查询$dep[x]+W_x$。
2.对于下行路径，大概画个图找个规律，你会发现是在插入$dep[t]?L$，查询$dep[x]?W_x$。
拆成两条链要用到倍增LCA，第二次统计的时后开两个$cnt$就好了。
时间复杂度:$O(n\log n)$。

实现

/*Lower_Rating*/
/*NOIP2016 天天爱跑步*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<vector>
#include<queue>
using namespace std;#define LL long long
#define DB double
#define MAXN 300000
#define MAXK 18
#define INF 2000000001
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}int n,m,ans[MAXN+5],stk1[MAXN*2+5],stk2[MAXN*2+5],w[MAXN+5];
int fa[MAXN+5][MAXK+1],dep[MAXN+5];
vector<int> G[MAXN+5];
vector<int> s1[MAXN+5],s2[MAXN+5],t1[MAXN+5],t2[MAXN+5];
void dfs(int x,int f){
    dep[x]=dep[f]+1;for(int i=0;i<G[x].size();i++){
    int v=G[x][i];if(v==f)continue;fa[v][0]=x;dfs(v,x);}
}
int LCA(int u,int v){
    if(dep[u]<dep[v])swap(u,v);for(int k=MAXK;k>=0;k--)if(dep[u]-dep[v]>=(1<<k))u=fa[u][k];if(u==v)return v;for(int k=MAXK;k>=0;k--)if(fa[u][k]!=fa[v][k])u=fa[u][k],v=fa[v][k];return fa[u][0];
}
void dfs2(int x,int f){
    ans[x]-=stk1[dep[x]+w[x]]+stk2[n+dep[x]-w[x]];for(int i=0;i<G[x].size();i++){
    int v=G[x][i];if(v==f)continue;dfs2(v,x);}for(int i=0;i<s1[x].size();i++)stk1[s1[x][i]]++;for(int i=0;i<s2[x].size();i++)stk2[s2[x][i]]++;for(int i=0;i<t1[x].size();i++)stk1[t1[x][i]]--;for(int i=0;i<t2[x].size();i++)stk2[t2[x][i]]--;ans[x]+=stk1[dep[x]+w[x]]+stk2[n+dep[x]-w[x]];
}
int main()
{
    n=read(),m=read();for(int i=1;i<n;i++){
    int u=read(),v=read();G[u].push_back(v);G[v].push_back(u);}for(int i=1;i<=n;i++)w[i]=read();dfs(1,0);for(int k=1;k<=MAXK;k++)for(int i=1;i<=n ;i++)fa[i][k]=fa[fa[i][k-1]][k-1];for(int i=1;i<=m;i++){
    int s=read(),t=read();int m1=LCA(s,t),m2=fa[m1][0];int L=dep[s]+dep[t]-2*dep[m1];s1[s].push_back(dep[s]);t1[m1].push_back(dep[s]);s2[t].push_back(dep[t]-L+n);t2[m2].push_back(dep[t]-L+n);}dfs2(1,0);for(int i=1;i<=n;i++)printf("%d ",ans[i]);
}