题意

有n个村庄，连成一棵树。

有m次操作，每次形如$u,v,w$,表示给从u到v的所有村庄颁发一个类型为w的证书，求每个村庄得到哪类证书的个数最多。若有多个输出类型最小值，若没有证书输出0

$n,m,w\le 10^5$

题解

先考虑链上怎么做。

因为证书类型很多，所以显然不能对每个证书差分记录。

但我们可以打标记，然后从前往后考虑每个点，每考虑到一个点把标记加上，然后计算。

计算的时候可以使用可以修改元素值的堆，每次加上一个标记就修改。

然后考虑回树上，显然是可以树链剖分成一条条重链的。

时间复杂度$O(n \log^2_2 n)$

代码

/*
Author: CNYALI_LK
LANG: C++
PROG: 5029.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
    int s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
char WriteIntBuffer[1024];
template<class T>void write(T a,char end){
    int cnt=0,fu=1;
    if(a<0){putchar('-');fu=-1;}
    do{WriteIntBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
    while(cnt){putchar(WriteIntBuffer[cnt]);--cnt;}
    putchar(end);
}
int beg[102424],to[233333],lst[233333],e;
void Add(int u,int v){
    to[++e]=v;
    lst[e]=beg[u];
    beg[u]=e;
    to[++e]=u;
    lst[e]=beg[v];
    beg[v]=e;
}
int siz[102424],hv[102424],hvy[102424];
void dfs1(int x,int fa){
//  debug("%d,%d\n",x,fa);
    siz[x]=1;hv[x]=0;
    for(int i=beg[x];i;i=lst[i])if(to[i]!=fa){
        dfs1(to[i],x);
        siz[x]+=siz[to[i]];
        if(siz[to[i]]>siz[hv[x]])hv[x]=to[i];
    }
}
int top[102424],dis[102424];
int ys[102424],fys[102424],fa[102424],t;
void dfs2(int x,int f){
    int k=ys[x]=++t;
    fys[t]=x;
    fa[t]=ys[f];
    if(hv[x]){  
        hvy[t]=t+1;
        top[t+1]=top[t];
        dis[t+1]=dis[t];
        dfs2(hv[x],x);
    }
    else hvy[t]=0;
    for(int i=beg[x];i;i=lst[i])if(to[i]!=f&&to[i]!=hv[x]){
        top[t+1]=t+1;
        dis[t+1]=dis[k]+1;  
        dfs2(to[i],x);
    }   
}

__gnu_pbds::priority_queue<pii> p;
__gnu_pbds::priority_queue<pii>::point_iterator iter[102424];
vector<pii> tags[102424];
void add(int u,int v,int w){
//  debug("Add %d start.\n",w);
    while(top[u]!=top[v]){
//      debug("Now u is %d,v is %d\n",u,v);
        if(dis[u]<dis[v])swap(u,v);
        tags[top[u]].push_back(make_pair(w,1));
        tags[u+1].push_back(make_pair(w,-1));
//      debug("%d->%d\n",top[u],u);
        u=fa[top[u]];
    }

    if(u>v){swap(u,v);}

//  debug("%d->%d\n",u,v);
    tags[u].push_back(make_pair(w,1));
    tags[v+1].push_back(make_pair(w,-1));
//  debug("Add %d end.\n",w);
}
const int N=100000;
int s[102424],ans[102424];
#define x first
#define y second
int main(){
#ifdef cnyali_lk
    freopen("5029.in","r",stdin);
    freopen("5029.out","w",stdout);
#endif
    int n,m;
    while(n=read()){
        m=read();
        t=0;
        for(int i=1;i<=n;++i)beg[i]=0,tags[i].erase(all(tags[i]));
        e=0;
        for(int i=1;i<n;++i){
            Add(read(),read()); 
        }
        dfs1(1,0);

        top[1]=1;
        dfs2(1,0);
        while(m){
            --m;
            int u,v,w;
            u=read();v=read();w=read();
            add(ys[u],ys[v],w);
        }

        while(!p.empty())p.pop();
        for(int i=1;i<=N;++i){
            iter[i]=p.push(make_pair(0,-i));    
            s[i]=0;
        }

        for(int i=1;i<=n;++i){
            for(vector<pii>::iterator it=tags[i].begin();it!=tags[i].end();++it){
                pii pix=*it;
                s[pix.x]+=pix.y;
                p.modify(iter[pix.x],make_pair(s[pix.x],-pix.x));
            }
            ans[fys[i]]=p.top().x?-p.top().y:0;
        }
        for(int i=1;i<=n;++i)printf("%d\n",ans[i]);
    }
    return 0;
}

标签: 树链剖分

添加新评论