TLE65pts线段树合并求调
查看原帖
TLE65pts线段树合并求调
48949
阿尔萨斯楼主2024/8/27 19:38
#include<bits/stdc++.h>
#define ll int
using namespace std;
ll read()
{
    ll s=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
        s=(s<<3)+(s<<1)+c-'0';
        c=getchar();
    }
    return s;
}
ll n,m,head[200005],fa[200005][20],dep[200005],tot=0,ans[200005],root[200005],lg[200005],ex[25];
struct kk{
    ll x,k;
    kk(){};
    kk(ll a,ll b)
    {
        x=a;
        k=b;
    }
};
vector<kk>tag[200005];
ll cnt=1,son[6400160][2],tree[6400160][2];
struct kkk{
    ll to,next;
}e[400005];
inline void add(ll x,ll y)
{
    tot++;
    e[tot].to=y;
    e[tot].next=head[x];
    head[x]=tot;
}
void build(ll s,ll pre)
{
    fa[s][0]=pre;
    ll now=1;
    for(ll i=1;i<=20;i++)
    {
        now<<=1;
        if(now>=dep[s])break;
        fa[s][i]=fa[fa[s][i-1]][i-1];
    }
    for(ll i=head[s];i;i=e[i].next)
    {
        ll to=e[i].to;
        if(to==pre)continue;
        dep[to]=dep[s]+1;
        build(to,s);
    }
}
ll lca(ll x,ll y)
{

    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]!=dep[y])x=fa[x][lg[dep[x]-dep[y]]];
    if(x==y)return x;
    ll now=0;
    while(fa[x][now]!=fa[y][now])now++;
    now--;
    while(fa[x][0]!=fa[y][0])
    {
        if(fa[x][now]!=fa[y][now])
        {
            x=fa[x][now];
            y=fa[y][now];
        }
        now--;
    }
    return fa[x][0];
}
void merge(ll x,ll y,ll l,ll r)
{
    if(tree[y][0]==0)return;
    if(l==r)
    {
        tree[x][0]+=tree[y][0];
        tree[x][1]=l;
        return;
    }
    ll mid=(l+r)>>1;
    if(son[x][0]||son[y][0])
    {
        if(son[x][0]&&son[y][0])merge(son[x][0],son[y][0],l,mid);
        else if(son[y][0])son[x][0]=son[y][0];
    }
    if(son[x][1]||son[y][1])
    {
        if(son[x][1]&&son[y][1])merge(son[x][1],son[y][1],mid+1,r);
        else if(son[y][1])son[x][1]=son[y][1];
    }
    if(!son[x][0])
    {
        tree[x][0]=tree[son[x][1]][0];
        tree[x][1]=tree[son[x][1]][1];
        return;
    }
    if(!son[x][1])
    {
        tree[x][0]=tree[son[x][0]][0];
        tree[x][1]=tree[son[x][0]][1];
        return;
    }
    if(tree[son[x][0]][0]>=tree[son[x][1]][0])
    {
        tree[x][0]=tree[son[x][0]][0];
        tree[x][1]=tree[son[x][0]][1];
    }
    else
    {
        tree[x][0]=tree[son[x][1]][0];
        tree[x][1]=tree[son[x][1]][1];
    }
}
void insert(ll s,ll l,ll r,ll x,ll k)
{
    if(l==r)
    {
        tree[s][0]+=k;
        tree[s][1]=l;
        return;
    }
    ll mid=(l+r)>>1;
    if(x<=mid)
    {
        if(!son[s][0])
        {
            cnt++;
            son[s][0]=cnt;
        }
        insert(son[s][0],l,mid,x,k);
    }
    else
    {
        if(!son[s][1])
        {
            cnt++;
            son[s][1]=cnt;
        }
        insert(son[s][1],mid+1,r,x,k);
    }
    if(!son[s][0])
    {
        tree[s][0]=tree[son[s][1]][0];
        tree[s][1]=tree[son[s][1]][1];
        return;
    }
    if(!son[s][1])
    {
        tree[s][0]=tree[son[s][0]][0];
        tree[s][1]=tree[son[s][0]][1];
        return;
    }
    if(tree[son[s][0]][0]>=tree[son[s][1]][0])
    {
        tree[s][0]=tree[son[s][0]][0];
        tree[s][1]=tree[son[s][0]][1];
    }
    else
    {
        tree[s][0]=tree[son[s][1]][0];
        tree[s][1]=tree[son[s][1]][1];
    }
}
void f(ll s,ll pre)
{
    cnt++;
    root[s]=cnt;
    for(ll i=head[s];i;i=e[i].next)
    {
        ll to=e[i].to;
        if(to==pre)continue;
        f(to,s);
        merge(root[s],root[to],1,100000);
    }
    for(ll i=0;i<tag[s].size();i++)
    {
        insert(root[s],1,100000,tag[s][i].x,tag[s][i].k);
    }
    if(tree[root[s]][0]==0)ans[s]=0;
    else ans[s]=tree[root[s]][1];
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ex[0]=1;
    for(ll i=1;i<=19;i++)ex[i]=ex[i-1]<<1;
    for(ll i=1;i<=100000;i++)
    {
        lg[i]=0;
        if(i>=ex[lg[i]+1])lg[i]++;
    }
    n=read();
    m=read();
    for(ll i=1;i<n;i++)
    {
        ll a,b;
        a=read();
        b=read();
        add(a,b);
        add(b,a);
    }
    dep[1]=1;
    build(1,0);
    for(ll i=1;i<=m;i++)
    {
        ll a,b,c;
        a=read();
        b=read();
        c=read();
        ll mylca=lca(a,b);
        tag[a].push_back(kk(c,1));
        tag[b].push_back(kk(c,1));
        tag[mylca].push_back(kk(c,-1));
        tag[fa[mylca][0]].push_back(kk(c,-1));
    }
    f(1,0);
    for(ll i=1;i<=n;i++)printf("%d\n",ans[i]);
}


2024/8/27 19:38
加载中...