HDU5029 Relief grain
题意
有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;
}