关于本题的lca
查看原帖
关于本题的lca
142549
hbhz_zcy楼主2022/3/29 16:24

我在本题的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;
}
2022/3/29 16:24
加载中...