萌新求助,2,3,4,5,11,13TLE了

P3038 [USACO11DEC] Grass Planting G

alone_lkx @ 2023-02-28 21:47:34

树链剖分+树状数组,不知道错在哪里,希望大佬出手相助,万分感谢!

#include<bits/stdc++.h>
using namespace std;
int n,m;
#define rank egweg
int const N=2e5+10;
struct edge{
    int u,v,w;
}e[N];
int cnt,first[N],nxt[N],rank[N],rt;
inline void add(int u,int v){
    e[++cnt].u=u;e[cnt].v=v;e[cnt].w=0;
    nxt[cnt]=first[u];first[u]=cnt;
}
int dep[N],fa[N],w[N],siz[N],son[N];
inline void dfs1(int u,int f){
    fa[u]=f;
    dep[u]=dep[f]+1;
    siz[u]=1;
    for(int i=first[u];i;i=nxt[i]){
        int v=e[i].v;
        if(v==f)continue;
        w[v]=e[i].w;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
int top[N],id[N],a[N],num;
inline void dfs2(int x,int topx){
    id[x]=++num;
    a[num]=w[x];
    top[x]=topx;
    if(son[x])dfs2(son[x],topx);
    for(int i=first[x];i;i=nxt[i]){
        int v=e[i].v;
        if(v==fa[x]||x==son[x])continue;
        dfs2(v,v);
    }
}
int c[N<<1];
inline int lowbit(int x){return x&(-x);}
inline void update(int k,int val){
    while(k<=num){
        c[k]+=val;
        k+=lowbit(k);
    }
}
inline void add_range(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(id[top[x]],1);
        update(id[x]+1,-1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(id[x]+1,1);
    update(id[y]+1,-1);
}
inline int query(int k){
    int ret=0;
    while(k){
        ret+=c[k];
        k-=lowbit(k);
    }
    return ret;
}
#define in read()
inline int read(){
    int k=1,x=0;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-')k=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return k*x;
}
int main(){
    freopen("P3038.in","r",stdin);
    freopen("P3038.ans","w",stdout);
    n=in;m=in;
    for(int i=1;i<n;i++){
        int u,v;
        u=in;v=in;
        rank[u]++;rank[v]++;
        add(u,v);
        add(v,u);
        if(rank[u]>rank[rt])rt=u;
        if(rank[v]>rank[rt])rt=v;
    }
    w[rt]=0;
    dfs1(rt,0);
    dfs2(rt,rt);
    for(int i=1;i<=num;i++){
        update(i,a[i]);
        update(i+1,-a[i]);
    }
    while(m--){
        char op;
        scanf(" %c",&op);
        int u=in,v=in;
        if(op=='P'){
            add_range(u,v);
        }
        else{
            if(dep[v]<dep[u])swap(u,v);
            printf("%d",query(id[v]));
        }
    } 
    return 0;
}

by CultReborn @ 2023-11-15 10:18:33

没想到吧!你的first没赋值,我调了半年终于调出来了


by CultReborn @ 2023-11-15 10:18:58

@alone_lkx


by alone_lkx @ 2023-11-15 18:27:19

@CultReborn 谢谢,已AC


|