60pts树剖 MLE求助
查看原帖
60pts树剖 MLE求助
162191
Dfkuaid楼主2021/2/1 08:57

这个 MLE 是哪个函数递归写炸了嘛。。。求查错QwQ

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 0x3fffffff
#define ll long long
#define mset(l,x) memset(l,x,sizeof(l))
#define mp(a,b) make_pair(a,b)
using namespace std;

const int N = 5e4+1e4;

struct Edge{
    int u;
    int v;
    int next;
};
Edge e[N << 1];

struct Node{
    int l,r;
    int ls,rs;
    int maxn;
    int lazy;
};
Node p[N << 2];

int n,m,cnt;
int head[N],top[N],id[N],rk[N];
int d[N],size[N],son[N],f[N];

inline void add_e(int u,int v){
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt ++;
}

inline void dfs1(int x,int fa,int depth){
    f[x] = fa;
    d[x] = depth;
    size[x] = 1;
    for (int i = head[x];i != -1;i = e[i].next){
        int v = e[i].v;
        if (v == fa)
          continue;
        dfs1(v,x,depth + 1);
        size[x] += size[v];
        if (size[v] > size[son[x]])
          son[x] = v;
    }
}

inline void dfs2(int x,int t){
    top[x] = t;
    id[x] = cnt;
    rk[cnt ++] = x;
    if (!son[x])
      return;
    dfs2(son[x],t);
    for (int i = head[x];i != -1;i = e[i].next){
        int v= e[i].v;
        if (v != f[x] && v != son[x])
          dfs2(v,v);
    }
}

inline int len(int k){
    return p[k].r - p[k].l + 1;
}

inline void pushup(int k){
    p[k].maxn = max(p[p[k].ls].maxn,p[p[k].rs].maxn);
}

inline void add(int k,int x){
    p[k].maxn += x;
    p[k].lazy += x;
}

inline void pushdown(int k){
    if (p[k].lazy){
        int ls = p[k].ls,rs = p[k].rs;
        add(ls,p[k].lazy);
        add(rs,p[k].lazy);
        p[k].lazy = 0;
//        pushup(k);
    }
}

inline void build(int k,int l,int r){
    if (l == r){
        p[k].maxn = 0;
        p[k].l = p[k].r = l;
        return;
    }
    int mid = (l + r) >> 1;
    p[k].ls = cnt ++;
    p[k].rs = cnt ++;
    build(p[k].ls,l,mid);
    build(p[k].rs,mid + 1,r);
    p[k].l = p[p[k].ls].l;
    p[k].r = p[p[k].rs].r;
    pushup(k);
}

inline void modify(int k,int l,int r,int x){
    if (l <= p[k].l && p[k].r <= r){
        add(k,x);
        return;
    }
    pushdown(k);
    int mid = (p[k].l + p[k].r) >> 1;
    if (mid >= l)
      modify(p[k].ls,l,r,x);
    if (mid < r)
      modify(p[k].rs,l,r,x);
    pushup(k);
}

inline int query(int k, int l,int r){
    if (l <= p[k].l && p[k].r <= r)
      return p[k].maxn;
    pushdown(k);
    int mid = (p[k].l + p[k].r) >> 1;
    int ans = -INF;
    if (mid >= l)
      ans = max(ans,query(p[k].ls,l,r));
    if (mid < r)
      ans = max(ans,query(p[k].rs,l,r));
    return ans;
}

inline void update(int x,int y){
    while (top[x] != top[y]){
        if (d[top[x]] < d[top[y]])
          swap(x,y);
        modify(0,id[top[x]],id[x],1);
        x = f[top[x]];
    }
    if (id[x] > id[y])
      swap(x,y);
    modify(0,id[x],id[y],1);
}

int main(){
    mset(head,-1);
    scanf("%d%d",&n,&m);
    for (int i = 1;i < n;i ++){
        int u,v;
        scanf("%d%d",&u,&v);
        add_e(u,v);
        add_e(v,u);
    }
    cnt = 0;
    dfs1(1,0,1);
    dfs2(1,1);
    cnt = 0;
    build(cnt ++,1,n);
    while (m --){
        int a,b;
        scanf("%d%d",&a,&b);
        update(a,b);
    }
//    for (int i = 0;i < cnt;i ++)
//      printf("%d [%d,%d] l:%d r:%d max:%d lazy%d\n",i,p[i].l,p[i].r,p[i].ls,p[i].rs,p[i].maxn,p[i].lazy);
    printf("%d",query(0,1,n));
    return 0;
}
2021/2/1 08:57
加载中...