题解：
win下的10mb和linux下的好像不是很一样 明天再看看
求lca用的离线求，注意bz数组开2*n
这道题的线段树合并还是很好想的
我们只要把操作差分一下就好了
时间复杂度nlogn的
写代码用时：1：30
对拍+maker+调错=30
看到网上题解用的是树剖。。
我看了很久很久才理解。。
以前我用树剖都没有去理解它变成序列这个本质。。
树剖保证了区间的连续性，所以差分对于不在同一段的完全没有影响
所以树剖完了就直接变成序列问题，非常强势啊
明天补
这样是nlognlogn的
正解：
#include <bits/stdc++.h>
using namespace std;
#define IL inline
#define rint register int
const int N=1.1e5;
char ss[<<],*A=ss,*B=ss;
IL char gc(){return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;}
template<class T>void read(T&x){
rint f=,c;while(c=gc(),c<||<c)if(c=='-')f=-;x=c^;
while(c=gc(),<c&&c<)x=(x<<)+(x<<)+(c^);x*=f;
}
IL void maxa(int &x,int y)
{
if (x>y) return;
else x=y;
}
IL void mina(int &x,int y)
{
if (x<y) return;
else x=y;
}
IL int max(int x,int y)
{
if (x>y) return(x); else return(y);
}
IL int min(int x,int y)
{
if (x<y) return(x); else return(y);
}
int n,m,fa[N],head[N],fi[N],root[N],cnt,cnt2,l,ans[N];
struct re{
int a,b;
}a[N*],b[N],c[N];
IL void arr(int x,int y)
{
a[++l].a=head[x];
a[l].b=y;
head[x]=l;
}
int id[N],dy[N],bz[][N*],pos[N],vt[N],fdy[N];
vector <int> ve1[N],ve2[N];
void dfs(int x)
{
id[x]=++cnt;
dy[cnt]=x;
bz[][++cnt2]=id[x];
pos[x]=cnt2;
int u=head[x];
while (u)
{
int v=a[u].b;
if (v!=fa[x])
{
fa[v]=x;
dfs(v);
bz[][++cnt2]=id[x];
}
u=a[u].a;
}
}
IL void swap(int &x,int &y)
{
int z=x; x=y; y=z;
}
IL int lca(int x,int y)
{
if (x==y) return(x);
x=pos[x],y=pos[y];
if (x>y) swap(x,y);
int z=log2(y-x+);
return(dy[min(bz[z][x],bz[z][y-(<<z)+])]);
}
struct segementree
{
int cnt;
int v[N*],p[N*],ls[N*],rs[N*];
segementree() { cnt=; }
#define mid ((h+t)/2)
IL void updata(int x)
{
v[x]=max(v[ls[x]],v[rs[x]]);
if (v[ls[x]]>v[rs[x]]||(v[ls[x]]==v[rs[x]]&&p[ls[x]]<p[rs[x]]))
p[x]=p[ls[x]];
else p[x]=p[rs[x]];
}
void change(int &x,int h,int t,int pos,int k)
{
if (!x) x=++cnt;
if (h==t)
{
v[x]+=k; p[x]=pos; return;
}
if (pos<=mid) change(ls[x],h,mid,pos,k);
else change(rs[x],mid+,t,pos,k);
updata(x);
}
int merge(int x,int y,int h,int t)
{
if (!x||!y) return(x^y);
ls[x]=merge(ls[x],ls[y],h,mid);
rs[x]=merge(rs[x],rs[y],mid+,t);
if (h==t) v[x]+=v[y];
else updata(x);
return(x);
}
}se1;
void dfs2(int x)
{
rint u=head[x];
while (u)
{
rint v=a[u].b;
if(v!=fa[x])
{
dfs2(v);
root[x]=se1.merge(root[x],root[v],,m);
}
u=a[u].a;
}
for (rint i=;i<ve1[x].size();i++)
se1.change(root[x],,m,ve1[x][i],);
for (rint i=;i<ve2[x].size();i++)
se1.change(root[x],,m,ve2[x][i],-);
if(!se1.v[root[x]]) ans[x]=;
else ans[x]=se1.p[root[x]];
}
IL bool cmp(re x,re y)
{
return(x.a<y.a);
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
read(n); read(m);
int x,y;
for (int i=;i<=n-;i++)
{
read(x); read(y); arr(x,y); arr(y,x);
}
dfs();
for (rint i=;i<=;i++)
for (rint j=;j<=cnt2;j++)
if ((<<(i-))+j-<=cnt2)
bz[i][j]=min(bz[i-][j],bz[i-][j+(<<(i-))]);
for( int i=;i<=m;i++)
{
read(c[i].a); read(c[i].b);
read(b[i].a); b[i].b=i;
}
sort(b+,b+m+,cmp);
b[].a=1e9;
int cnt3=;
for (int i=;i<=m;i++)
{
if (b[i].a!=b[i-].a)
{
cnt3++;
fdy[cnt3]=b[i].a;
}
vt[b[i].b]=cnt3;
}
for (int i=;i<=m;i++)
{
int x=c[i].a,y=c[i].b,z=vt[i];
// cout<<x<<" "<<y<<" "<<z<<" ";
int xx=lca(x,y);
//cout<<xx<<endl;
ve1[x].push_back(z);
ve1[y].push_back(z);
ve2[xx].push_back(z);
ve2[fa[xx]].push_back(z);
}
dfs2();
for (int i=;i<=n;i++)
{
printf("%d\n",fdy[ans[i]]);
}
return ;
}
//离散化
拍：
#include <bits/stdc++.h>
using namespace std;
const int N=1e3;
int v[N][N];
int head[N],n,m,l;
struct re{
int a,b;
}a[N*];
void arr(int x,int y)
{
a[++l].a=head[x];
a[l].b=y;
head[x]=l;
}
int cnt=,id[N],dy[N],fa[N];
void dfs(int x,int fa1)
{
int u=head[x];
id[x]=++cnt;
dy[cnt]=x;
while (u)
{
int v=a[u].b;
if (v!=fa1) fa[v]=x,dfs(v,x);
u=a[u].a;
}
}
const int INF=1e9;
bool pd(int x,int y)
{
while (x!=y&&x) x=fa[x];
if(x==y) return(); else return();
}
int lca(int x,int y)
{
int ans=;
for (int i=;i<=n;i++)
if (pd(x,i)&&pd(y,i)) ans=max(ans,id[i]);
return(dy[ans]);
}
int main()
{
freopen("1.in","r",stdin);
freopen("2.out","w",stdout);
cin>>n>>m;
for (int i=;i<=n-;i++)
{
int x,y;
cin>>x>>y;
arr(x,y); arr(y,x);
}
dfs(,);
for (int i=;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
int xx=lca(x,y);
for (int i=x;i!=fa[xx];i=fa[i]) v[i][z]++;
for (int i=y;i!=fa[xx];i=fa[i]) v[i][z]++;
v[xx][z]--;
}
for (int i=;i<=n;i++)
{
int ans=,ans2=;
for (int j=;j<=;j++)
if(v[i][j]>ans) ans=v[i][j],ans2=j;
cout<<ans2<<endl;
}
return ;
}
数据：
#include <bits/stdc++.h>
using namespace std;
int main()
{
freopen("1.in","w",stdout);
int n=,m=;
cout<<n<<" "<<m<<endl;
srand(time());
for (int i=;i<=n;i++)
{
int x=rand()%(i-)+;
cout<<x<<" "<<i<<endl;
}
for (int i=;i<=m;i++)
{
int x=rand()%n+,y=rand()%n+,z=rand()%+;
cout<<x<<" "<<y<<" "<<z<<endl;
}
}