求助
查看原帖
求助
820867
Sun_liwei楼主2024/8/31 10:43

请问这个为什么会TLE?

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10;
int n,m,ts;
int siz[N],son[N],top[N],dep[N],fa[N],id[N];
vector<vector<int>> a(N);
int tr[N];//树状数组
int lowbit(int x){
    return x & -x;
}
void add(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)){
        tr[i] += c;
    }
}
int sum(int x){
    int ans = 0;
    for(int i=x;i;i-=lowbit(i)) ans += tr[i];
    return ans;
}
void update(int l,int r){
    add(l,1),add(r+1,-1);
}
void dfs1(int u,int father){
    dep[u] = dep[father] + 1,siz[u] = 1,fa[u] = father;
    for(auto v : a[u]){
        if(v == father) continue;
        dfs1(v,u);
        siz[u] += siz[v];
        if(siz[son[u]] < siz[v]) son[u] = v;
    }
}
void dfs2(int u,int t){
    top[u] = t;//t为所在重链的链头
    if(son[u] == 0) return;
    //搜重儿子
    dfs2(son[u],t);
    //搜轻儿子
    for(auto v : a[u]){
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v,v);
    }
}
void modify(int u,int v){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u,v);
        update(id[top[u]],id[u]);
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u,v);
    update(id[u],id[v]);
}
void solve(){
    cin >> n >> m;
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs1(1,0);dfs2(1,1);
    while(m --){
        int u,v;
        cin >> u >> v;
        modify(u,v);
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        ans = max(ans,sum(i));
    }
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T --) solve();
    return 0;
}
2024/8/31 10:43
加载中...