『树上差分·线段树合并』「NOIP2016」天天爱跑步

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

我们对于任意路线$[s,t]$来说，可以分为$[s,\mathrm{L}\mathrm{c}\mathrm{a}(s,t)]$和$(\mathrm{L}\mathrm{c}\mathrm{a}(s,t),t]$两部分。

• 对于$x$属于第一部分，满足条件必然有：$de{p}_s?w_x=de{p}_x$
  也就是：$$de{p}_s=de{p}_x+w_x$$
• 对于$x$属于第二部分，满足条件必然有：$de{p}_s+de{p}_x?2de{p}_{\mathrm{L}\mathrm{c}\mathrm{a}(s,t)}=w_x$
  变形一下有：$$de{p}_{\mathrm{L}\mathrm{c}\mathrm{a}(s,t)}\times 2?de{p}_s=de{p}_x?w_x$$

我们以第一种情况为例：$de{p}_s=de{p}_x+w_x$相当于为路线$[s,\mathrm{L}\mathrm{c}\mathrm{a}(s,t)]$上的每一个点丢一个$de{p}_s$的物品.每次查询有多少个物品种类为$w_x?de{p}_x$即可。

我们知道经过了一系列转化以后，问题转化为了雨天的尾巴，我们可以采用树上差分+线段树合并来解决。

我们可以用数组$cnt[x][v]$表示节点$x$中权值$v$的出现次数。

由于暴力修改的时间复杂度过高，但由于这是路径修改，我们可以考虑树上差分。

由于修改的只是一条链，即$\mathrm{L}\mathrm{c}\mathrm{a}(x,y)=y$时，只要$cnt[x][v]+1$,$cnt[f{a}_y][v]?1$即可。

然后就是难写难调的线段树合并惹…

代码如下：

#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;
const int N = 300010;
const int LOG = 25;
const int M = 3e5 * 4 * 20;int n, m;
int tot = 0;
int w[N], f[N][LOG], dep[N], val[M], lc[M], rc[M], ans[N], root[N];
vector <int> a[N];int read(void)
{
    int s = 0, w = 0; char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}void dfs(int x,int fa)
{
    dep[x] = dep[fa] + 1;for (int i=0;i<a[x].size();++i){
    int y = a[x][i];if (y == fa) continue;f[y][0] = x, dfs(y,x);}return; 
}void dp(void)
{
    for (int j=1;j<=20;++j)for (int i=1;i<=n;++i)f[i][j] = f[f[i][j-1]][j-1];return;
}int LCA(int x,int y)
{
    if (dep[x] < dep[y]) swap(x,y);for (int i=0,d=dep[x]-dep[y];i<=20;++i)if ((d >> i) & 1) x = f[x][i];if (x == y) return x;for (int i=20;i>=0;--i)  if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];return f[x][0];
}void insert(int &p,int l,int r,int x,int v)
{
    if (p == 0) p = ++ tot;if (l == r) return val[p] += v, void();int mid = l + r >> 1;if (x <= mid) insert(lc[p],l,mid,x,v);if (x > mid) insert(rc[p],mid+1,r,x,v);return;
}int merge(int p,int q,int l,int r)
{
    if (!p || !q) return p + q;if (l == r) return val[p] += val[q], p;int mid = l + r >> 1;lc[p] = merge(lc[p],lc[q],l,mid);rc[p] = merge(rc[p],rc[q],mid+1,r);return p;	
}int query(int p,int l,int r,int x)
{
    if (l == r) return val[p];int mid = l + r >> 1;if (x <= mid) return query(lc[p],l,mid,x);if (x > mid) return query(rc[p],mid+1,r,x);
}#define in(pos) (pos >= 1 and pos <= n * 2) void dfs2(int x,int fa)
{
    for (int i=0;i<a[x].size();++i){
    int y = a[x][i];if (y == fa) continue;dfs2(y,x);root[x] = merge(root[x],root[y],1,n<<1);}if(w[x] && in(n+dep[x]+w[x]))ans[x] += query(root[x],1,n<<1,n+dep[x]+w[x]);ans[x] += query(root[x],1,n<<1,n+dep[x]-w[x]);return;
}int main(void)
{
    freopen("running.in","r",stdin);freopen("running.out","w",stdout);n = read(), m = read();for (int i=1,x,y;i<n;++i){
    x = read(), y = read();a[x].push_back(y);a[y].push_back(x);}dfs(1,0), dp(); for (int i=1;i<=n;++i) w[i] = read();while (m --){
    int s = read(), t = read();int Lca = LCA(s,t);insert(root[s],1,n<<1,n+dep[s],1);insert(root[Lca],1,n<<1,n+dep[s],-1);insert(root[t],1,n<<1,n+2*dep[Lca]-dep[s],1);if (Lca^1) insert(root[f[Lca][0]],1,n<<1,n+2*dep[Lca]-dep[s],-1);}dfs2(1,0);for (int i=1;i<=n;++i) printf("%d ", ans[i]);return 0; 
}