洛谷P1600 天天愛跑步（線段樹合并）

小c同學認為跑步非常有趣,于是決定制作一款叫做《天天愛跑步》的遊戲。《天天愛跑步》是一個養成類遊戲,需要玩家每天按時上線,完成打卡任務。

這個遊戲的地圖可以看作一一棵包含 nn個結點和 n-1n−1條邊的樹, 每條邊連接配接兩個結點,且任意兩個結點存在一條路徑互相可達。樹上結點編号為從11到nn的連續正整數。

現在有mm個玩家,第ii個玩家的起點為 S_iS

i

​ ,終點為 T_iT

​ 。每天打卡任務開始時,所有玩家在第00秒同時從自己的起點出發, 以每秒跑一條邊的速度, 不間斷地沿着最短路徑向着自己的終點跑去, 跑到終點後該玩家就算完成了打卡任務。 (由于地圖是一棵樹, 是以每個人的路徑是唯一的)

小c想知道遊戲的活躍度, 是以在每個結點上都放置了一個觀察員。 在結點jj的觀察員會選擇在第W_jW

j

​ 秒觀察玩家, 一個玩家能被這個觀察員觀察到當且僅當該玩家在第W_jW

​ 秒也理到達了結點 jj 。 小C想知道每個觀察員會觀察到多少人?

注意: 我們認為一個玩家到達自己的終點後該玩家就會結束遊戲, 他不能等待一 段時間後再被觀察員觀察到。 即對于把結點jj作為終點的玩家: 若他在第W_jW

​ 秒前到達終點,則在結點jj的觀察員不能觀察到該玩家;若他正好在第W_jW

​ 秒到達終點,則在結點jj的觀察員可以觀察到這個玩家。

輸入輸出格式

輸入格式：

第一行有兩個整數nn和mm 。其中nn代表樹的結點數量, 同時也是觀察員的數量, mm代表玩家的數量。

接下來 n- 1n−1行每行兩個整數uu和 vv,表示結點 uu到結點 vv有一條邊。

接下來一行 nn個整數,其中第jj個整數為W_jW

​ , 表示結點jj出現觀察員的時間。

接下來 mm行,每行兩個整數S_iS

​ ,和T_iT

​ ,表示一個玩家的起點和終點。

對于所有的資料,保證1\leq S_i,T_i\leq n, 0\leq W_j\leq n1≤S

​ ,T

​ ≤n,0≤W

​ ≤n 。

輸出格式：

輸出1行 nn個整數,第jj個整數表示結點jj的觀察員可以觀察到多少人。

輸入輸出樣例

輸入樣例#1：

6 3

2 3

1 2

1 4

4 5

4 6

0 2 5 1 2 3

1 5

1 3

2 6

輸出樣例#1：

2 0 0 1 1 1

輸入樣例#2：

5 3

2 3

2 4

0 1 0 3 0

3 1

1 4

5 5

輸出樣例#2：

1 2 1 0 1

題解：号稱提高組最難一題，其實難度還行

考慮把一個人的路徑拆成起點到lca和lca到終點兩段，差分一下用線段樹維護

具體的操作是對起點插入deep起點，終點插入2*deep[lca]-deep起點，相當于把起點沿lca翻上去。

然後線段樹合并一波就搞定了

查詢的是每個點deep+wj和deep-wj距離的點有幾個

其實線段樹合并是大材小用了，如果對每個點查詢li-ri時間之間有多少人經過顯然才更妙

代碼如下：

#include<bits/stdc++.h>
#define lson tr[now].l
#define rson tr[now].r
using namespace std;

struct tree
{
    int l,r,sum;
} tr[20000010];

vector<int> g[300010];
vector<int> op1[300010],op2[300010];
int n,m,ans[300010],q[300010],rt[300010],deep[300010],fa[300010][20],cnt;
int N=600000;

int dfs(int now,int f,int dep)
{
    deep[now]=dep;
    fa[now][0]=f;
    rt[now]=now;
    ++cnt;
    for(int i=1; i<=19; i++)
    {
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
    for(int i=0; i<g[now].size(); i++)
    {
        if(g[now][i]==f) continue;
        dfs(g[now][i],now,dep+1);
    }
}

int lca(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=19; i>=0; i--)
    {
        if(deep[fa[x][i]]>=deep[y]) x=fa[x][i];
    }
    if(x==y) return x;
    for(int i=19; i>=0; i--)
    {
        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}

int push_up(int now)
{
    tr[now].sum=tr[lson].sum+tr[rson].sum;
}

int insert(int &now,int l,int r,int pos,int val)
{
    if(!now) now=++cnt;
    if(l==r)
    {
        tr[now].sum+=val;
        return 0;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)
    {
        insert(lson,l,mid,pos,val);
    }
    else
    {
        insert(rson,mid+1,r,pos,val);
    }
    push_up(now);
}

int query(int now,int l,int r,int pos)
{
    if(l==r) return tr[now].sum;
    int mid=(l+r)>>1;
    if(pos<=mid) return query(lson,l,mid,pos);
    else return query(rson,mid+1,r,pos);
}

int merge(int a,int b,int l,int r)
{
    if(!b) return a;
    if(!a) return b;
    if(l==r)
    {
        tr[a].sum+=tr[b].sum;
        return a;
    }
    int mid=(l+r)>>1;
    tr[a].l=merge(tr[a].l,tr[b].l,l,mid);
    tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);
    push_up(a);
    return a;
}

int solve(int now,int f)
{
    for(int i=0; i<op1[now].size(); i++)
    {
        insert(rt[now],0,N,op1[now][i],1);
    }
    for(int i=0; i<op2[now].size(); i++)
    {
        insert(rt[now],0,N,op2[now][i],-1);
    }
    for(int i=0; i<g[now].size(); i++)
    {
        if(g[now][i]==f) continue;
        solve(g[now][i],now);
        merge(rt[now],rt[g[now][i]],0,N);
    }
    if(deep[now]+n-q[now]>=0) ans[now]+=query(rt[now],0,N,deep[now]+n-q[now]);
    if(deep[now]+n+q[now]<=N&&q[now]!=0) ans[now]+=query(rt[now],0,N,deep[now]+n+q[now]);
}

int main()
{
    int from,to;
    scanf("%d%d",&n,&m);
    for(int i=1; i<n; i++)
    {
        scanf("%d%d",&from,&to);
        g[from].push_back(to);
        g[to].push_back(from);
    }
    for(int i=1; i<=n; i++) scanf("%d",&q[i]);
    dfs(1,0,1);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&from,&to);
        int anc=lca(from,to);
        op1[from].push_back(deep[from]+n);
        op1[to].push_back(n-(deep[from]-deep[anc])+deep[anc]);
        op2[anc].push_back(deep[from]+n);
        op2[fa[anc][0]].push_back(n-(deep[from]-deep[anc])+deep[anc]);
    }
    solve(1,0);
    for(int i=1;i<=n;i++)
    {
        printf("%d ",ans[i]);
    }
}