【线段树】[LUOGU NOIP2016 天天爱跑步] 线段树合并+树上差分

题目：

题目链接：[LUOGU NOIP2016 天天爱跑步]
题解：
（这个题，，真的，其实学这个权值线段树的知识，就是为了写这道题的，，，但是，尽管半个小时码完了代码，但是，，，调了一下午，，，，o(╥﹏╥)o）
不扯了，还是好好写题解吧：

这道题其实就是个加强版的雨天的尾巴（树上差分+线段树合并），可以先做一下这道题。
这个题中的链中，如果可以被观察员发现的话，需要满足两点：

第一点：$x$点在子树中在$lca(Si,Ti)$之下的时候，而且要满足$deep[Si]?deep[x]=w[x];$

第二点：$x$点在$lca(Si,Ti)$和$Ti$之间（不含$lca(si,ti)$），而且要满足$deep[Si]+deep[Ti]+deep[x]?2?deep[lca(si,ti)]=w[x];$
这样的话再开两个vector，记录“显示”和“消失”，这就是树上差分的操作了（这里可以参考雨天的尾巴）然后就是线段树合并了。

其实这里是线段树合并的大材小用了，如果可以查询在$L$到$R$之中的观察的人树，这样的话更能显现出权值线段树的好处了。

代码：

（太痛苦了，，，，，就是一个LCA，，，改换板子了，之前的板子不仅不是太好写非常的冗杂，而且，，，还有什么玄学错误，因为这个，，我，，调了一下午o(╥﹏╥)o）

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
} 
const int sea=3e5+7;
const int ocean=6e5+7;
vector<int>show[sea],vani[sea];
struct see{
    int ver,next;}e[ocean];
struct hit{
    int ls,rs,sum,ans;}tr[sea*40];
int n,m,seg,tot,root[sea],deep[sea],fa[22][sea],w[sea],last[ocean];
void add(int x,int y){
    e[++tot].next=last[x];e[tot].ver=y;last[x]=tot;}
void DFS(int x,int f,int d)
{
    deep[x]=d;fa[0][x]=f; root[x]=x; ++seg;for(int i=1;i<=19;i++) fa[i][x]=fa[i-1][fa[i-1][x]];for(int i=last[x];i;i=e[i].next)if(e[i].ver!=f) DFS(e[i].ver,x,d+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[i][x]]>=deep[y])x=fa[i][x];if(x==y) return x;for(int i=19;i>=0;i--) if(fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];return fa[0][x];
}
void build(int &k,int l,int r,int val,int tt)
{
    if(!k) k=++seg;if(l==r){
    tr[k].sum+=tt; return ;}int mid=(l+r)/2;if(val<=mid) build(tr[k].ls,l,mid,val,tt);else build(tr[k].rs,mid+1,r,val,tt);tr[k].sum=tr[tr[k].ls].sum+tr[tr[k].rs].sum;
}
int incor(int x,int y,int l,int r)
{
    if(!x) return y; if(!y) return x;if(l==r){
    tr[x].sum+=tr[y].sum; return x;}int mid=(l+r)/2;tr[x].ls=incor(tr[x].ls,tr[y].ls,l,mid);tr[x].rs=incor(tr[x].rs,tr[y].rs,mid+1,r);tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum;return x;
}
int ask(int k,int l,int r,int val)
{
    if(l==r) return tr[k].sum;int mid=(l+r)/2;if(val<=mid) return ask(tr[k].ls,l,mid,val);else return ask(tr[k].rs,mid+1,r,val);
}
void dfs(int x,int fa)
{
    for(int i=0;i<show[x].size();i++) build(root[x],1,ocean,show[x][i],1);for(int i=0;i<vani[x].size();i++) build(root[x],1,ocean,vani[x][i],-1);for(int i=last[x];i;i=e[i].next){
    int y=e[i].ver; if(y==fa) continue;dfs(y,x); root[x]=incor(root[x],root[y],1,ocean);}if(deep[x]+n>=w[x]) tr[x].ans+=ask(root[x],1,ocean,deep[x]+n-w[x]);if(deep[x]+n+w[x]<=ocean&&w[x]) tr[x].ans+=ask(root[x],1,ocean,deep[x]+n+w[x]);
}
int main()
{
    n=read(); m=read();for(int i=1,x,y;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);for(int i=1;i<=n;i++) w[i]=read(); DFS(1,0,1); for(int i=1;i<=m;i++){
    int x=read(),y=read(),ins=lca(x,y);show[x].push_back(deep[x]+n);show[y].push_back(n+2*deep[ins]-deep[x]);vani[ins].push_back(deep[x]+n);vani[fa[0][ins]].push_back(n+2*deep[ins]-deep[x]); }dfs(1,0); for(int i=1;i<=n;i++) printf("%d ",tr[i].ans);return 0;
}

Continue……