柠檬树

https://ac.nowcoder.com/acm/problem/212478

莫队超时改了半天块的大小没xx用

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
using namespace std;
const int N = 2e5+10, M = 4e5+10;
int n, m, len, tot;
int h[N], e[M], nxt[M], idx;
int res[N];
set<int> id;
int dfn[N], rdfn[N], tim;
struct Query{
    int id, l, r;
}q[N];
int dep[N], fa[N][20];
int getid(int x)
{
    return x / len;
}
void add(int a,int b)
{
    e[idx] = b, nxt[idx] = h[a], h[a] = idx ++;
}
bool cmp(Query &a, Query &b)
{
    int x = getid(a.l), y = getid(b.l);
    if(x != y) return x < y;
    if(x % 2) return a.r < b.r;
    return a.r > b.r;
}
void dfs(int u,int f)
{
    dfn[u] = ++ tim; rdfn[tim] = u;
    for(int i = h[u]; ~i; i = nxt[i])
    {
        int to = e[i];
        if(to == f || dfn[to]) continue;
        dfs(to, u);
    }
}
void bfs(int s)
{
    queue<int> q;
    memset(dep, 0x3f, sizeof dep);
    dep[0] = 0, dep[s] = 1;
    q.push(s);
    while(q.size())
    {
        int u = q.front(); q.pop();
        for(int i = h[u]; ~i; i = nxt[i])
        {
            int to = e[i];
            if(dep[to] > dep[u] + 1)
            {
                dep[to] = dep[u] + 1;
                q.push(to);
                fa[to][0] = u;
                for(int k = 1; k < 20; ++ k) 
                    fa[to][k] = fa[fa[to][k - 1]][k - 1];
            }
        }
    }
}
int lca(int a, int b)
{
    if(dep[a] < dep[b]) swap(a, b);
    for(int k = 19; k >= 0; k --)
        if(dep[fa[a][k]] >= dep[b]) a = fa[a][k];

    if(a == b) return a;
    for(int k = 19; k >= 0; k --)
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}
void del(int tree_id)
{
    int dfn_id = dfn[tree_id];
    if(!dfn_id) return;
    if(id.empty())
    {
        id.insert(dfn_id);
        return;
    }

    auto r = id.upper_bound(dfn_id);
    if(r == id.end()) r = id.begin();
    auto l = --id.upper_bound(dfn_id);
    if(l == id.begin()) l = --id.end();
    else l --;

    int x = rdfn[*r], y = rdfn[*l], z = rdfn[dfn_id];
    tot -= 2 * dep[z] - 2 * dep[lca(x, z)] - 2 * dep[(lca(y, z))] + 2 * dep[lca(x, y)];
    id.erase(id.lower_bound(dfn_id));

}
void add(int tree_id)
{
    int dfn_id = dfn[tree_id];
    if(!dfn_id) return;
    if(id.empty())
    {
        id.insert(dfn_id);
        return;
    }
    auto r = id.upper_bound(dfn_id);
    if(r == id.end()) r = id.begin();
    auto l = id.upper_bound(dfn_id);
    if(l == id.begin()) l = --id.end();
    else l --;

     int x = rdfn[*r], y = rdfn[*l], z = rdfn[dfn_id];
     tot += 2 * dep[z] - 2 * dep[lca(x, z)] - 2 * dep[(lca(y, z))] + 2 * dep[lca(x, y)];
     id.insert(dfn_id);

}
void print()
{
    auto r = id.upper_bound(2);
    if(r == id.end()) r = id.begin();
    auto l = id.upper_bound(2);
    if(l == id.begin()) l = --id.end();
    else l --;
    printf("%d %d\n", *r, *l);
}
int dis(int a, int b)
{
    int p = lca(a, b);
    return dep[a] + dep[b] - 2 * dep[p];
}
int main()
{
    // id.insert(0); 
    // id.insert(1e9);
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    len = sqrt(n * n / m);
    for(int i = 0; i < n - 1; ++ i)
    {
        int a, b; scanf("%d%d", &a, &b);
        add(a, b); add(b, a);
    }
    dfs(1, -1);
    bfs(1);

    for(int i = 0; i < n; ++ i)
    {
        int l, r; scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }
    sort(q, q + m, cmp);
    int i = 1, j = 0;
    //print(2);
    for(int k = 0; k < m; ++k)
    {
        int id = q[k].id, l = q[k].l, r = q[k].r;
        //printf("%d %d %d\n", id, l, r);
        while(i > l) add(i - 1), i --;

        while(j < r) add(j + 1), j ++; 
        while(i < l) del(i), i ++; 
        while(j > r) del(j), j --;
        res[id] = tot / 2;
    }
    for(int i = 0; i < m; ++ i) printf("%d\n", res[i]);

}

LCT
难的东西唯一的缺点就是难...

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e6+10;
int n, ans[N];
struct Query{
    int id, l, r;
    bool operator <(Query &b)const
    {
        return r <b.r;
    }
}querys[N];

int h[N], e[N], nxt[N], idx;
void add(int a,int b)
{
    e[idx] = b, nxt[idx] = h[a], h[a] = idx ++;
}
namespace LCA{
    int lca(int ,int);
}
namespace treeArray{
    #define lowbit(x) (-x & x)
    int s[N];
    void add(int x, int p)
    {
        x ++;
        for(int i = x; i <= n + 1; i += lowbit(i)) s[i] += p;
    }
    int sum(int x)
    {
        x ++;
        int ans = 0;
        for(; x; x -= lowbit(x) ) ans += s[x];
        return ans;
    }
}
namespace segTree{
    #define ls u << 1
    #define rs u << 1 | 1
    #define mid (L + R >> 1)
    int t[N];
    void pushup(int u)
    {
        t[u] = LCA::lca(t[ls], t[rs]);
    }
    void build(int u, int L, int R)
    {
        t[u] = L;
        if(L == R) return;
        build(ls, L, mid); build(rs, mid +1, R);
        pushup(u);
    }
    int query(int l, int r,int u, int L, int R)
    {
        if(l <= L && R <= r) return t[u];
        if(r <= mid) return query(l, r, ls, L, mid);
        if(l > mid) return query(l, r, rs, mid + 1, R);
        return LCA::lca(query(l, r, ls, L, mid), query(l, r, rs, mid +1, R));
    }
}
namespace LCA{
    const int K = 20;
    int fa[N][K], dep[N];
    void dfs(int u, int father)
    {
        dep[u] = dep[father] + 1; fa[u][0] = father; 
        for(int k = 1; k < K; ++ k) fa[u][k] = fa[fa[u][k - 1]][k - 1];

        for(int i = h[u]; ~i; i = nxt[i])
        {
            int to = e[i];
            if(to == father) continue;
            dfs(to, u);
        }
    }
    int lca(int a,int b)
    {
        if(dep[a] < dep[b]) swap(a, b);
        for(int k = K - 1; k >= 0; k --)
            if(dep[fa[a][k]] >= dep[b]) a = fa[a][k];
        if(a == b) return a;
        for(int k = K - 1; k >= 0; k --) if(fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k];
        return fa[a][0];
    }
    int deplca(int l, int r)
    {
        return dep[segTree::query(l, r, 1, 1, n)];
    }
}
namespace LCT{
    struct Node{int s[2], p, v, siz, tag;} t[N];
    int stk[N], top;
    void dfs(int u, int father)
    {
        t[u].p = father;
        for(int i = h[u]; ~i; i = nxt[i])
        {
            int to = e[i];
            if(to == father) continue;
            dfs(to, u);
        }
    }
    void pushup(int u)
    {
        t[u].siz = t[t[u].s[0]].siz + t[t[u].s[1]].siz + 1;
    }
    void addtag(int u,int v)
    {
        t[u].tag = t[u].v = v;
    }
    void pushdown(int u)
    {
        if(t[u].tag)
        {
            addtag(t[u].s[0], t[u].tag); addtag(t[u].s[1], t[u].tag);
            t[u].tag = 0;
        }
    }
    bool isroot(int x)
    {
        return t[t[x].p].s[0] != x && t[t[x].p].s[1] != x;
    }
    void rotate(int x)
    {
        int y = t[x].p, z = t[y].p, k = t[y].s[1] == x;
        if(!isroot(y)) t[z].s[t[z].s[1] == y] = x; t[x].p = z;
        t[y].s[k] = t[x].s[k ^ 1]; t[t[x].s[k ^ 1]].p = y;
        t[x].s[k ^ 1] = y; t[y].p = x;
        pushup(y); pushup(x);
    }
    void splay(int x)
    {
        int bak = x; stk[top = 1] = x;
        while(!isroot(bak)) stk[++ top] = bak = t[bak].p;
        while(top) pushdown(stk[top --]);
        while(!isroot(x))
        {
            int y = t[x].p, z = t[y].p;
            if(!isroot(y))
                if(t[y].s[1] == x ^ t[z].s[1] == y) rotate(x);
            else rotate(y);
            rotate(x);
        }
    }
    void access(int x)
    {
        int col = x, y = 0;
        for(; x; y = x, x = t[x].p)
        {
            splay(x);
            treeArray::add(t[x].v, -(t[t[x].s[0]].siz + 1));
            t[x].s[1] = y; pushup(x);
        }

        treeArray::add(col, t[y].siz);
        addtag(y, col);
    }
}
using treeArray::sum;
using LCT::access;
using LCA::deplca;
int main()
{
    //freopen("1.txt", "r", stdin);
    memset(h, -1, sizeof h);

    int m; scanf("%d%d", &n, &m);

    for(int i = 1;  i < n; ++i)
    {
        int a, b; scanf("%d%d", &a, &b);
        add(a, b); add(b, a);
    }

    for(int i = 0; i < m; ++i)
    {
        int l, r; scanf("%d%d", &l, &r);
        querys[i] = {i, l, r};
    }
    LCA::dfs(1, 0); segTree:: build(1, 1, n);
    LCT::dfs(1, 0);
    sort(querys, querys + m);
    int j = 0;
    treeArray::add(0, n);
    for(int i = 1; i <= n; ++ i)
    {
        access(i);
        for(; j < m && querys[j].r == i; ++ j)
            ans[querys[j].id] = n - sum(querys[j].l - 1) - deplca(querys[j].l, querys[j].r);
    }
    for(int i = 0; i < m; ++i) printf("%d\n", ans[i]);
}