_WA自动机的blog

过期高中生。

[luogu P1600][NOIP 2016]天天爱跑步

发表于 更新于 分类于 阅读次数： Valine：

树上差分+线段树合并

题目大意

小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\)的观察员可以观察到这个玩家。
其中，\(n,m\le 3\times 10^5\)

题解：

每一个结点都有观察者...
这道题主要的难点在于推贡献...我做这题的时候将人的行走看做了修改，一直拘泥于如何快速维护树上路径加等差数列...这样显然不太可做...
我们考虑什么样的路径会对一个点\(w\)的观察者有贡献：

  • 路径的两个端点（记为\(u,v\)）至少有一个在\(w\)的子树内

  • \(\text{lca}(u,v)\)不在w的子树内

  • 对于u在w子树内的情况： \[\text{depth}(u)-\text{depth}(w)=\mathcal{W}\]

  • 对于v在w子树内的情况： \[\text{depth}(u)-2*\text{depth}(\text{lca}(u,v))+\text{depth}(w)=\mathcal{W}\] 所以，我们有三个限制条件...不太好做... 对于u,v限制条件不同的情况，我们显然可以分类讨论，这不是啥问题.. 这里最麻烦的一点是\(\text{lca}(u,v)\)不在w的子树内..似乎不好维护呢~

但是我们还有一个有力武器！树上差分！ 我们把\(u\rightarrow v\)的路径拆分成 \(u->lca\ lca->v\)，进一步差分成\(u\rightarrow root ,v\rightarrow root,root\rightarrow lca,root\rightarrow fa[lca]\)，其中前两条路径权值为+1，后两条路径权值为-1.这样，我们就摆脱了lca的限制，一个节点的整个子树都可以对它产生贡献，就可以直接树上统计了！

现在，每一个节点的答案由它的子树得到，每个子树相互独立并且可合并...线段树合并！再分类讨论u和v的贡献，就做完啦！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using std::vector;

const int maxn=3e5+100;

vector<int> G[maxn];
int count[maxn],w[maxn];
int s[maxn],t[maxn];
int depth[maxn],fa[maxn],siz[maxn];
int top[maxn],son[maxn];
int ans[maxn],tag[maxn],tot;
int root[maxn];

struct Node
{
    int ls,rs,siz;
}T[maxn*50];

template<class T>inline void swap(T& a,T& b){a^=b^=a^=b;}

inline int Newnode(){T[++tot].ls=0;T[tot].rs=0;T[tot].siz=0;return tot;}

inline int insert(int pos,int rt,int l,int r,int val=1)
{
    if (!rt) rt=Newnode();
    T[rt].siz+=val;
    if (l==r) return rt;
    int mid=(l+r)>>1;
    if (pos<=mid) T[rt].ls=insert(pos,T[rt].ls,l,mid,val);
    else T[rt].rs=insert(pos,T[rt].rs,mid+1,r,val);
    return rt;
}

inline int merge(int x,int y)
{
    if (!x || !y) return x+y;
    T[x].siz+=T[y].siz;
    T[x].ls=merge(T[x].ls,T[y].ls);
    T[x].rs=merge(T[x].rs,T[y].rs);
    return x;
}

inline int query(int pos,int l,int r,int rt)
{
    if (!rt) return 0;
    if (l==r) return T[rt].siz;
    int mid=(l+r)>>1;
    if (pos<=mid) return query(pos,l,mid,T[rt].ls);
    else return query(pos,mid+1,r,T[rt].rs);
}

inline void dfs(int u,int ff,int dep)
{
    depth[u]=dep;
    fa[u]=ff;siz[u]=1;
    int maxs=-1;
    for (auto v:G[u])
    {
        if (v==ff) continue;
        dfs(v,u,dep+1);
        siz[u]+=siz[v];
        if (siz[v]>=maxs) maxs=siz[v],son[u]=v;
    }
}

inline void dfs(int u,int topf)
{
    top[u]=topf;
    if (!son[u]) return;
    dfs(son[u],topf);
    for (auto v:G[u]) 
        if (v!=fa[u] && v!=son[u]) dfs(v,v);
}

inline int LCA(int u,int v)
{
    while (top[u]!=top[v])
    {
        if (depth[top[u]]<depth[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return depth[u]>depth[v]?v:u;
}

inline void dfs_cal1(int u,int n)
{
    for (auto v:G[u])
        if (v!=fa[u]) dfs_cal1(v,n),root[u]=merge(root[u],root[v]);
    ans[u]+=query(depth[u]+w[u],1,n,root[u]);
}

inline void dfs_cal2(int u,int n)
{
    for (auto v:G[u])
        if (v!=fa[u]) dfs_cal2(v,n),root[u]=merge(root[u],root[v]);
    ans[u]+=query(w[u]-depth[u],-n*2,n,root[u]);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1,u,v;i<n;++i)
        scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
    for (int i=1;i<=n;++i)
        scanf("%d",w+i);
    for (int i=1;i<=m;++i)
        scanf("%d%d",s+i,t+i);
    dfs(1,0,1);dfs(1,1);
    static int lca[maxn];
    for (int i=1,u,v;i<=m;++i)
    {
        u=s[i];v=t[i];
        lca[i]=LCA(u,v);
        root[u]=insert(depth[u],root[u],1,n<<1);
        root[fa[lca[i]]]=insert(depth[u],root[fa[lca[i]]],1,n<<1,-1);
    }
    dfs_cal1(1,n<<1);
    tot=0;memset(root,0,sizeof(root));
    for (int i=1,u,v;i<=m;++i)
    {
        u=s[i],v=t[i];
        root[v]=insert(depth[u]-2*depth[lca[i]],root[v],-2*n,n);
        root[lca[i]]=insert(depth[u]-2*depth[lca[i]],root[lca[i]],-2*n,n,-1);
    }
    dfs_cal2(1,n);
    for (int i=1;i<=n;++i)
        printf("%d ",ans[i]);
}