我在本题的lca中,取ceil:100;直接int:45;取floor:15。
请问为什么。
(代码中是l2i函数)
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1e5+10,maxlogn=20;//all keeps back
int N,M,root[maxn],fa[maxn][20],d[maxn],head[maxn],nume=0,numf=0,ans[maxn],vis[maxn];
struct node{int l,r,v,p;}f[maxlogn*(maxn<<2)];
struct node2{int to,nxt;}e[maxn<<1];
int qd(){
int rt=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while('0'<=c&&c<='9') rt=(rt<<3)+(rt<<1)+c-48,c=getchar();
return rt;
}
void edgen(int from,int to){
e[++nume].nxt=head[from];
head[from]=nume;
e[nume].to=to;
}
int l2i(int x){return ceil(log2(x));}
int lca(int x,int y){
if(d[x]<d[y]) swap(x,y);
while(d[x]>d[y])
x=fa[x][max(0,l2i(d[x]-d[y])-1)];
if(x==y) return x;
for(int k=max(l2i(d[x])-1,0);k>=0;k--)
if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];
return fa[x][0];
}
void pushup(int t){
int l=f[t].l,r=f[t].r;
f[t].v=max(f[l].v,f[r].v);
f[t].p=(f[t].v?(f[l].v>=f[r].v?f[l].p:f[r].p):0);
// printf("%d:%d %d %d %d\n",t,l,r,f[t].p,f[t].v);
}
void add(int &t,int p,int v,int l,int r){
if(!t) t=++numf;
if(l==r){f[t].v+=v;f[t].p=p;return;}
int m=(l+r)>>1;
if(p<=m) add(f[t].l,p,v,l,m);
else add(f[t].r,p,v,m+1,r);
pushup(t);
}
void mg(int &t,int t0,int l,int r){
if(!t){t=t0;return;}
f[t].v+=f[t0].v;
// if(l==r) printf(" %d:%d %d %d %d\n",t,l,r,f[t].p,f[t].v);
if(l==r) return;
int m=(l+r)>>1;
if(f[t0].l) mg(f[t].l,f[t0].l,l,m);
if(f[t0].r) mg(f[t].r,f[t0].r,m+1,r);
pushup(t);
}
void dfs1(int u,int depth){
d[u]=depth;
for(int i=1;i<=l2i(depth);i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(fa[u][0]!=v){fa[v][0]=u;dfs1(v,depth+1);}
}
}
void dfs2(int u){
// printf("dfs %d\n",u);
for(int i=head[u];i;i=e[i].nxt)
if(e[i].to!=fa[u][0]) dfs2(e[i].to),mg(root[u],root[e[i].to],1,maxn);
ans[u]=f[root[u]].p;
// printf("%d:%d %d\n",u,f[root[u]].p,f[root[u]].v);
}
int main(){
N=qd(),M=qd();
for(int i=1;i<N;i++){
int x=qd(),y=qd();
edgen(x,y);edgen(y,x);
}
dfs1(1,1);
// for(int i=1;i<=N;i++){
// for(int j=0;j<=2;j++){
// printf("%d %d:%d\n",i,j,fa[i][j]);
// }
// }
for(int i=1;i<=M;i++){
int x=qd(),y=qd(),z=qd(),xy=lca(x,y);
add(root[xy],z,-1,1,maxn);
if(fa[xy][0]) add(root[fa[xy][0]],z,-1,1,maxn);
add(root[x],z,1,1,maxn);add(root[y],z,1,1,maxn);
// printf("%d %d ++ \n%d %d -- \n",x,y,xy,fa[xy][0]);
//[1,x]++,[1,y]++,[1,lca(x,y))-2,lca(x,y)--;
//all moves first then val;
}
// for(int i=1;i<=N;i++) printf("%d %d %d\n",i,f[root[i]].p,f[root[i]].v);
dfs2(1);
for(int i=1;i<=N;i++) printf("%d\n",ans[i]);
return 0;
}