线段树合并模板,已 AC 但求助
查看原帖
线段树合并模板,已 AC 但求助
613794
jianhe楼主2025/7/31 15:37

rt,只把下面代码中的第 25,2625,26 行注释掉就能过,但是只把第 27,2827,28 行注释掉就连样例都过不去,不知道为什么,理论上结构体内和结构体外的变量不是等价的吗?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const ll N=1e5+10,M=1e5;
ll n,m,x,y,z,ct,ans[N],d[N],f[N][22],s[N<<5][2];
vector<ll> e[N],q[N];
void dfs(ll x,ll fa){
    d[x]=d[fa]+1,f[x][0]=fa;
    for(int i=1;i<=20;i++) f[x][i]=f[f[x][i-1]][i-1];
    for(auto y:e[x])
        if(y!=fa) dfs(y,x);
}
ll lca(ll x,ll y){
    if(d[x]<d[y]) swap(x,y);
    for(int i=20;~i;i--)
        if(d[f[x][i]]>=d[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=20;~i;i--)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
struct T{ll ls=0,rs=0,a=0,b=0;bool operator<(const T& B)const{return b==B.b?a>B.a:b<B.b;}}t[N<<5];
#define mid (l+r>>1)
#define ls(x) t[x].ls
#define rs(x) t[x].rs
#define ls(x) s[x][0]
#define rs(x) s[x][1]
void up(ll rt){t[rt]=max(t[ls(rt)],t[rs(rt)]);}
void update(ll rt,ll l,ll r,ll x,ll y){
    if(l==r){t[rt].a=x,t[rt].b+=y;return;}
    if(x<=mid){
        if(!ls(rt)) ls(rt)=++ct;
        update(ls(rt),l,mid,x,y);
    }else{
        if(!rs(rt)) rs(rt)=++ct;
        update(rs(rt),mid+1,r,x,y);
    }
    up(rt);
}
void merge(ll rt,ll rt2,ll l,ll r){
    if(l==r){t[rt].b+=t[rt2].b;return;}
    if(ls(rt2)) ls(rt)?merge(ls(rt),ls(rt2),l,mid):(void)(ls(rt)=ls(rt2));
    if(rs(rt2)) rs(rt)?merge(rs(rt),rs(rt2),mid+1,r):(void)(rs(rt)=rs(rt2));
    up(rt);
}
void dfs2(ll x,ll fa){
    for(auto y:e[x])
        if(y!=fa) dfs2(y,x),merge(x,y,1,M);
    for(auto z:q[x]) update(x,1,M,abs(z),z>0?1:-1);
    ans[x]=t[x].a;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;ct=n;
    for(int i=1;i<n;i++) cin>>x>>y,e[x].pb(y),e[y].pb(x);
    dfs(1,0);
    while(m--){
        cin>>x>>y>>z;ll l=lca(x,y);
        q[x].pb(z),q[y].pb(z),q[l].pb(-z),q[f[l][0]].pb(-z);
    }
    dfs2(1,0);
    for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
    return 0;
}
2025/7/31 15:37
加载中...