[luogu4556]雨天的尾巴

luogu

发现是一顿子修改然后再询问,那么把修改树上差分一下再线段树合并

但是...

如果你只有35分...

https://www.luogu.org/discuss/show/88259

#include<bits/stdc++.h>

using namespace std;

const int _=1e5+5;

int re(){

    int x=0,w=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*w;

}

int n,m,cnt,N=1e5,tot;

int h[_],f[_],a[_],b[_],z[_],fa[_],lca[_],rt[_],ans[_];

int mx[_*67],id[_*67],ls[_*67],rs[_*67];

bool vis[_];

vector<int>p[_];

struct edge{int to,next;}e[_<<1];

void link(int u,int v){

    e[++cnt]=(edge){v,h[u]};h[u]=cnt;

    e[++cnt]=(edge){u,h[v]};h[v]=cnt;

}

int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

void dfs(int u){

    for(int i=h[u];i;i=e[i].next){

        int v=e[i].to;

        if(v==fa[u])continue;

        fa[v]=u;dfs(v);f[v]=u;

    }

    vis[u]=1;

    for(int i=0,j=p[u].size();i<j;i++){

        int k=p[u][i],v=a[k]==u?b[k]:a[k];

        if(vis[v])lca[k]=find(v);

    }

}

void pu(int x){

    mx[x]=max(mx[ls[x]],mx[rs[x]]);

    if(mx[ls[x]]==mx[rs[x]])id[x]=min(id[ls[x]],id[rs[x]]);

    else id[x]=mx[ls[x]]>mx[rs[x]]?id[ls[x]]:id[rs[x]];

}

void upd(int&x,int l,int r,int k,int v){

    if(!x)x=++tot;

    if(l==r){mx[x]+=v;id[x]=l;return;}

    int mid=(l+r)>>1;

    if(k<=mid)upd(ls[x],l,mid,k,v);

    else upd(rs[x],mid+1,r,k,v);pu(x);

}

int merge(int a,int b,int l,int r){

    if(!a||!b)return a|b;

    if(l==r)mx[a]+=mx[b];

    else{

        int mid=(l+r)>>1;

        ls[a]=merge(ls[a],ls[b],l,mid);

        rs[a]=merge(rs[a],rs[b],mid+1,r);

        pu(a);

    }return a;

}

void solve(int u){

    for(int i=h[u];i;i=e[i].next){

        int v=e[i].to;

        if(v==fa[u])continue;

        solve(v);

        rt[u]=merge(rt[u],rt[v],1,N);

    }

    ans[u]=id[rt[u]];

}

int main(){

    n=re();m=re();

    for(int i=1;i<=n;i++)f[i]=i;

    for(int i=1,u,v;i<n;i++){

        u=re(),v=re();link(u,v);

    }

    for(int i=1;i<=m;i++){

        a[i]=re(),b[i]=re();z[i]=re();

        p[a[i]].push_back(i);

        p[b[i]].push_back(i);

    }

    dfs(1);

    for(int i=1;i<=m;i++){

        upd(rt[a[i]],1,N,z[i],1);

        upd(rt[b[i]],1,N,z[i],1);

        upd(rt[lca[i]],1,N,z[i],-1);

        upd(rt[fa[lca[i]]],1,N,z[i],-1);

    }

    solve(1);

    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);

    return 0;

}

巴特西

[luogu4556]雨天的尾巴

[luogu4556]雨天的尾巴

最新文章

热门文章