• 题面描述
    • 在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员\(Blue\ Mary\)也开始骑着摩托车传递邮件了。不过，她经常回忆起以前在乡间漫步的情景。昔日，乡下有依次编号为\(1..n\)的\(n\)个小村庄，某些村庄之间有一些双向的土路。从每个村庄都恰好有一条路径到达村庄\(1\)（即比特堡）。并且，对于每个村庄，它到比特堡的路径恰好只经过编号比它的编号小的村庄。另外，对于所有道路而言，它们都不在除村庄以外的其他地点相遇。在这个未开化的地方，从来没有过高架桥和地下铁道。随着时间的推移，越来越多的土路被改造成了公路。至今，\(Blue\ Mary\)还清晰地记得最后一条土路被改造为公路的情景。现在，这里已经没有土路了——所有的路都成为了公路，而昔日的村庄已经变成了一个大都市。 \(Blue\ Mary\)想起了在改造期间她送信的经历。她从比特堡出发，需要去某个村庄，并且在两次送信经历的间隔期间,有某些土路被改造成了公路.
    • 现在\(Blue\ Mary\)需要你的帮助：计算出每次送信她需要走过的土路数目。（对于公路，她可以骑摩托车；而对于土路，她就只好推车了。）
  • 输入格式
    • 第一行是一个数\(n(1 \leq n \leq 25*10^4)\).以下\(n-1\)行，每行两个整数\(a\)，\(b\)\((1 \leq a< b\leq n)\)以下一行包含一个整数\(m(1 \leq m \leq 25*10^4)\)，表示\(Blue\ Mary\)曾经在改造期间送过\(m\)次信。以下\(n+m-1\)行，每行有两种格式的若干信息，表示按时间先后发生过的\(n+m-1​\)次事件:
      • 若这行为 \(A\ a\ b\ (a<b)\) ，表示\(a\)到\(b\)的一条直接连边从土路变成公路
      • 若这行为 \(W\ a\), 则表示\(Blue\ Mary\)曾经从比特堡送信到村庄\(a\)。
  • 输出格式
    • 有\(m\)行，每行包含一个整数，表示对应的某次送信时经过的土路数目。
  • 题解
    • 清新小水题
    • 用\(dfn\)序维护子树信息，一次操作就变为对一个区间\(-1\)，询问是单点查询
    • 用线段树常数不好的话会被卡\(TLE\)，用树状数组就稳过了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=5e5+5;
const int MAXM=1e6+6;
int edge,head[MAXN],tail[MAXM],nex[MAXM];
int dfn[MAXN],cnt,id[MAXN];
int out[MAXN];
int d[MAXN];
int n,m;
int t[MAXN];
void add_e(int u,int v){
    edge++,nex[edge]=head[u],head[u]=edge,tail[edge]=v;
}
void add(int x,int val){
    for (;x<=n;x+=x&-x) t[x]+=val;
}
int sum(int x){
    int ret=0;
    for (;x;x-=x&-x) ret+=t[x];
    return ret;
}
void dfs(int u,int p){
    dfn[u]=++cnt; id[cnt]=u; d[u]=d[p]+1;
    for (int e=head[u];e;e=nex[e]){
        int v=tail[e];
        if (v==p) continue;
        dfs(v,u);
    }
    out[u]=cnt;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<n;i++){
        int u,v; scanf("%d%d",&u,&v);
        add_e(u,v); add_e(v,u);
    }
    d[0]=-1; dfs(1,0);
    scanf("%d",&m);
    for (int i=1;i<n+m;i++){
        char op=getchar(); while (op!='W'&&op!='A') op=getchar();
        if (op=='W'){
            int u; scanf("%d",&u);
            printf("%d\n",sum(dfn[u])+d[u]);
        }
        else {
            int u,v; scanf("%d%d",&u,&v);
            add(out[v]+1,1); add(dfn[v],-1);
        }
    }
    return 0;
}
  • \(TLE\)的线段树版
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=5e5+5;
const int MAXM=1e6+6;
int edge,head[MAXN],nex[MAXM],tail[MAXM];
int dfn[MAXN],cnt,id[MAXN];
int out[MAXN],d[MAXN];
int n,m,M,rt;
struct tnode{
    int l,r,cl,cr,dat,tag;
} t[MAXN];
void add(int u,int v){
    edge++,nex[edge]=head[u],head[u]=edge,tail[edge]=v;
}
int newnode(int l,int r,int cl,int cr,int dat){
    t[++M]=(tnode){l,r,cl,cr,dat,0};
    return M;
}
int build(int l,int r){
    if (l==r) return newnode(l,r,0,0,d[id[l]]);
    int mid=(l+r)>>1;
    int cl=build(l,mid),cr=build(mid+1,r);
    return newnode(l,r,cl,cr,t[cl].dat+t[cr].dat);
}
void pushdown(int id){
    int cl=t[id].cl,cr=t[id].cr;
    int tag=t[id].tag;
    if (!tag) return;
    t[id].dat+=tag;
    t[cl].tag+=tag;
    t[cr].tag+=tag;
    t[id].tag=0;
}
void update(int id){
    int cl=t[id].cl,cr=t[id].cr;
    t[id].dat=t[cl].dat+t[cr].dat;
}
void modify(int a,int b,int id,int val){
    pushdown(id);
    int l=t[id].l,r=t[id].r;
    int cl=t[id].cl,cr=t[id].cr;
    if (l>b||r<a) return;
    if (a<=l&&r<=b){
        t[id].tag+=val;
        pushdown(id);
        return;
    }
    modify(a,b,cl,val); modify(a,b,cr,val);
    update(id);
}
int query(int a,int b,int id){
    pushdown(id);
    int l=t[id].l,r=t[id].r;
    int cl=t[id].cl,cr=t[id].cr;
    if (l>a||r<a) return 0;
    if (a<=l&&r<=b) return t[id].dat;
    return query(a,b,cl)+query(a,b,cr);
}
void dfs(int u,int p){
    dfn[u]=++cnt; id[cnt]=u; d[u]=d[p]+1;
    for (int e=head[u];e;e=nex[e]){
        int v=tail[e];
        if (v==p) continue;
        dfs(v,u);
    }
    out[u]=cnt;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<n;i++){
        int u,v; scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
    }
    dfs(1,0);
    rt=build(1,n);
    scanf("%d",&m);
    for (int i=1;i<n+m;i++){
        char op=getchar(); while (op!='W'&&op!='A') op=getchar();
        if (op=='W'){
            int u; scanf("%d",&u);
            printf("%d\n",query(dfn[u],dfn[u],rt)-1);
        }
        else {
            int u,v; scanf("%d%d",&u,&v);
            modify(dfn[v],out[v],rt,-1);
        }
    }
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄