求问站外（玄关）

题目描述

树之国有

n

个城市，编号为

1

到

n

，

n-1

条无向道路连接着这些城市，任意两个城市之间都可以互相到达。有

m

个商人在树之国进行着商业活动，第

i

个商人会在

x_i

号城市到

y_i

号城市的简单路径（包括

x_i

号和

y_i

号城市）上活动。如果两个商人的活动范围有重合，他们可以进行交易，请你对每个商人求出有多少个商人可以和他交易。

输入格式

第一行两个正整数

n, m

。
接下来

n-1

行，每行两个正整数，表示一条道路的两个端点。
接下来

m

行，每行两个正整数，其中第

i

行为

x_i, y_i

。

输出格式

输出

m

行，每行一个整数，其中第

i

行表示有多少个其他商人能和第

i

个商人交易。

样例输入

TEXT

样例输出

TEXT

1
2
1

数据规模与约定

对于 $20\%$ 的数据， $n, m \le 200$ 。
对于 $50\%$ 的数据， $n, m \le 5000$ 。
另有 $20\%$ 的数据，第 $i$ 条边连接 $i$ 和 $i+1$ 。
对于 $100\%$ 的数据， $1 \le n, m \le 2 \times 10^5$ 。

我的代码

CPP

#include<iostream>
#include<vector>
#include<cctype>
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline char getc() {
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
    int x = 0, f = 1;
    char ch = getc();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getc();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getc();
    }
    return x * f;
}
inline void write(int x) {
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
using namespace std;
int n,m;
const int N = 2e5 + 4;
vector<int> G[N];
int top[N],hson[N],siz[N];
int idx,dfn[N],f[N],dep[N];
int cnt[N],ans[N];
pair<int,int> v[N];
inline int max(int a,int b){
    return a > b ? a : b;
}
inline int min(int a,int b){
    return a > b ? b : a;
}
inline void Dfs1(int u,int fa){
    dep[u] = dep[fa] + 1;
    siz[u] = 1,f[u] = fa;
    hson[u] = -1;
    for(auto v : G[u]){
        if(v == fa)  continue;
        Dfs1(v,u);
        siz[u] += siz[v];
        if(hson[u] == -1)  hson[u] = v;
        else if(siz[hson[u]] < siz[v])  hson[u] = v;
    }
}
inline void Dfs2(int u,int t){
    dfn[u] = ++ idx;
    top[u] = t;
    if(hson[u] != -1){
        Dfs2(hson[u],t);
    }
    for(auto v : G[u]){
        if(v == hson[u] || v == f[u])   continue;
        Dfs2(v,v);
    }
}

struct segment{
    int l,r,sum,tag;
}t[N * 4];
inline void pushup(int p){
    t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
}
inline void pushdown(int p){
    if(t[p].tag == 0)  return ;
    t[p << 1].tag += t[p].tag;
    t[p << 1 | 1].tag += t[p].tag;
    t[p << 1].sum += (t[p << 1].r - t[p << 1].l + 1) * t[p].tag;
    t[p << 1 | 1].sum += (t[p << 1 | 1].r - t[p << 1 | 1].l + 1) * t[p].tag;
    t[p].tag = 0;
}
inline void build(int p,int l,int r){
    t[p].l = l,t[p].r = r;
    if(l == r)  return ;
    int mid = l + r >> 1;
    build(p << 1,l,mid),build(p << 1 | 1,mid + 1,r);
}
inline void add(int p,int l,int r){
    if(t[p].l >= l && t[p].r <= r){
        t[p].sum += t[p].r - t[p].l + 1;
        t[p].tag ++;
        return ;
    }
    pushdown(p);
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid)
        add(p << 1,l,r);
    if(r > mid)
        add(p << 1 | 1,l,r);
    pushup(p);
}
inline int qry(int p,int l,int r){
    if(t[p].l >= l && t[p].r <= r)  return t[p].sum;
    pushdown(p);
    int res = 0;
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid)  res += qry(p << 1,l,r);
    if(r > mid)  res += qry(p << 1 | 1,l,r);
    return res;
}



inline int flca(int x,int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])   swap(x,y);
        x = f[top[x]];
    }
    int l = (dep[x] > dep[y] ? y : x);
    cnt[l] ++;
    return l;
}
inline int lca(int x,int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])   swap(x,y);
        x = f[top[x]];
    }
    int l = (dep[x] > dep[y] ? y : x);
    return l;
}
inline int qlca(int x,int y){
    int res = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])   swap(x,y);
        res += qry(1,dfn[top[x]],dfn[x]);
        x = f[top[x]];
    }
    res += qry(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]));
    return res;
}
inline void alca(int x,int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])   swap(x,y);
        add(1,dfn[top[x]],dfn[x]);
        x = f[top[x]];
    }
    add(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]));
}
int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    n = read(),m = read();
    for(register int i = 1;i < n;i += 1){
        int u = read(),v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    Dfs1(1,0);
    Dfs2(1,1);
    build(1,1,n);
    for(register int i = 1;i <= m;i += 1){
        v[i].first = read(),v[i].second = read();
    }
    for(register int i = 1;i <= m;i += 1){
        int l = flca(v[i].first,v[i].second);
        alca(l,l);
    }
    int tim = 0;
    for(register int i = 1;i <= m;i += 1){
        ans[tim] += qlca(v[i].first,v[i].second);
        tim ++;
    }
    for(register int i = 1; i <= 4 * n; i += 1){
        t[i].sum = 0;
        t[i].tag = 0;
    }
    for(register int i = 1;i <= m;i += 1){
        alca(v[i].first,v[i].second);
    }
    tim = 0;
    for(register int i = 1;i <= m;i += 1){
        int l = lca(v[i].first,v[i].second);
        ans[tim] += qlca(l,l);
        write( ans[tim] - 1 - cnt[l] );
        putchar('\n');
        tim ++;
    }
}

但是卡不过去常，他们说可以树上差分，求问怎么做或者你也可以帮我卡卡常thx

求问站外（玄关）

讨论操作

题目描述

输入格式

输出格式

样例输入

样例输出

数据规模与约定

回复

相关推荐

求问站外（玄关）