记录编号	589271	评测结果	AAAAAAAAAA
题目名称	飘雪圣域	最终得分	100
用户昵称	liuyiche	是否通过	通过
代码语言	C++	运行时间	2.561 s
提交时间	2024-07-04 16:05:30	内存使用	8.53 MiB

#include <bits/stdc++.h>  
                         
using namespace std;

int n, m, now = 0;

struct node
{
    vector<int> nxt;
};
vector<node> v(200005);
int p[200005];
int cnt[200005];
int fa[200005];

struct node2
{
    int l;
    int r;
    int id;
    int blo;
    int ans;
};
node2 q[200005];

inline bool cmp(node2 a, node2 b)
{
    return a.l < b.l;
}
inline bool cmp2(node2 a, node2 b)
{
    if(a.blo%2 == 1)
        return a.r < b.r;
    else  return a.r > b.r;
}

inline void build()
{
    int block = sqrt(m);
    int num = m/block;
    if(m%block != 0)
        num++;
    for(int i = 1; i <= num; ++i)
    {
        int l = (i-1)*block+1;
        int r = i*block;
        r = min(r,m);
        for(int j = l; j <= r; ++j)
            q[j].blo = i;
        sort(q+l,q+r+1,cmp2);
    }
}

inline void dfs(int step, int last)
{
    for(int i = 0; i < v[step].nxt.size(); ++i)
    {
        if(v[step].nxt[i] == last)
            continue;
        fa[v[step].nxt[i]] = step;
        dfs(v[step].nxt[i],step);
    }
}

inline void add(int pos)
{
    int tmp = cnt[pos];
    tmp += p[fa[pos]];
    now -= tmp;
    now++;
    p[pos]++;
    cnt[fa[pos]]++;
}
 
inline void del(int pos)
{
    int tmp = cnt[pos];
    tmp += p[fa[pos]];
    now += tmp;
    now--;
    p[pos]--;
    cnt[fa[pos]]--;
}

inline bool cmp3(node2 a, node2 b)
{
    return a.id < b.id;
}
                      
int main()
{
    freopen("icekingdom.in", "r", stdin);
    freopen("icekingdom.out", "w", stdout);
        	
   	ios::sync_with_stdio(false);
   	cin.tie(0); cout.tie(0); 
        	
    cin >> n >> m;
    for(int i = 1; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        v[x].nxt.push_back(y);
        v[y].nxt.push_back(x);
    }
    
    for(int i = 1; i <= m; ++i)
    {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q+1,q+m+1,cmp);
   	build();
   	dfs(1,0);
    int l = 1, r = 0;
    for(int i = 1; i <= m; ++i)
    {
        int ql = q[i].l, qr = q[i].r;
        while(l < ql)  del(l++);
        while(l > ql)  add(--l);
        while(r < qr)  add(++r);
        while(r > qr) del(r--);
        q[i].ans = now;
    }
    
    sort(q+1,q+m+1,cmp3);
    for(int i = 1; i <= m; ++i)
        cout << q[i].ans << '\n';
   	
    return 0;
}