主席树95分

开 O2 就 TLE

不开就 MLE

试过在不开的情况下只把一点点变量改成 long long 没什么用

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int _ = 3e5 + 5;

inline int read()
{
    int w = 1,f = 0;
    char c = getchar();
    while(c < '0' or c > '9'){if(c == '-') w = -1;c = getchar();}
    while(c >= '0' and c <= '9'){f = f * 10 + c - '0';c = getchar();}
    return w * f;
}

struct node
{
    int l,r,ls,rs,sum;
    node(){l = r = ls = rs = sum = 0;}
    node(int _l,int _r,int _ls,int _rs,int _sum):l(_l),r(_r),ls(_ls),rs(_rs),sum(_sum){}
}a[_ << 5];

int n,q;
vector <int> G[_];
int siz[_],dep[_],dfn[_],_dfn;
int init[_],cnt,rt[_];

void dfs(int u,int fa)
{
//  cout << "FUCKING " << u << " " << fa << endl;

    dep[u] = dep[fa] + 1;
    dfn[u] = ++_dfn;
    siz[u] = 1;
    for(int v : G[u])
    {
        if(v == fa)
            continue;
        dfs(v,u);
        siz[u] += siz[v];
    }
}

int build(int l,int r)
{
    int k = ++cnt;
    a[k].l = l,a[k].r = r;
    if(l == r) return k;
    int mid = (l + r) >> 1;
    a[k].ls = build(l,mid);
    a[k].rs = build(mid + 1,r);
    return k;
}

int update(int pre,int x,int y)
{
    int k = ++cnt;
    a[k] = a[pre];
    if(a[k].l == a[k].r)
    {
        a[k].sum += y;
        return k;
    }
    int mid = (a[k].l + a[k].r) >> 1;
    if(x <= mid)
        a[k].ls = update(a[k].ls,x,y);
    if(x > mid)
        a[k].rs = update(a[k].rs,x,y);
    a[k].sum = a[a[k].ls].sum + a[a[k].rs].sum;
    return k;
}

int query(int k,int l,int r)
{
//  if(k == 0)
//      exit(0);
//  cout << k << " " << a[k].l << " " << a[k].r << endl;
    if(a[k].l >= l and a[k].r <= r)
        return a[k].sum;
    int mid = (a[k].l + a[k].r) >> 1,sum = 0;
    if(l <= mid)
        sum += query(a[k].ls,l,r);
    if(r > mid)
        sum += query(a[k].rs,l,r);
    return sum;
}

signed main()
{
    n = read();
    q = read();
    for(int i = 1;i < n;i++)
    {
        int u,v;
        u = read();
        v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    for(int i = 1;i <= n;i++)
        init[dfn[i]] = i;
    //_______________________________
//  cout << "dfn: ";
//  for(int i = 1;i <= n;i++)
//      cout << dfn[i] << " ";
//  cout << endl << "init:";
//  for(int i = 1;i <= n;i++)
//      cout << init[i] << " ";
//  cout << endl;
    //_______________________________
    rt[0] = build(1,n);
    for(int i = 1;i <= n;i++)
        rt[i] = update(rt[i - 1],dep[init[i]],siz[init[i]] - 1)/*,printf("FUCKing : %d - > %d \n",i,query(rt[i],1,4))*/;
    while(q--)
    {
        int p = read(),k = read(),ans = 0;

        ans += min(dep[p] - 1,k) * (siz[p] - 1);
//      cout << "FUCK1 " << query(rt[dfn[p] + siz[p] - 1],1,4) << endl;
//      cout << "FUCK2 " << query(rt[dfn[p]],1,4) << endl;
        ans += query(rt[dfn[p] + siz[p] - 1],dep[p] + 1,dep[p] + k);
        ans -= query(rt[dfn[p]],             dep[p] + 1,dep[p] + k);//bug : dep[p + 1];
        printf("%lld\n",ans);
    }
    return 0;
}