砍树(详细注释)--先暴力--再树链剖分+树差分优化

解题思路:

满足条件的边一定是每组数据都要经过的公共边

例如：3 6；4 5；那满足条件的边一定既是3到6的路径又是4到5的路径，那这条边权值一定为m；再选出最大编号的边
注意事项:

参考代码:

暴力(只能过一部分)：

#includeusing namespace std;
typedef pair pii;
const int N = 1e5+10;
map id;//记录边的编号 
vectoredge[N];//记录图 
int n,m,w[N];//w[i]为某边的权值 i为边的编号 
bool v[N];//访问标记 

bool dfs(int st,int ed){//st起点ed终点 dfs将st到ed所经过的所有边权值加1 
	for(int i=0;in>>m;
	memset(w,0,sizeof(w)); 
	for(int i=1;i>x>>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
		id[{x,y}] = id[{y,x}] = i;
	}
	for(int i=0;i>x>>y;
		memset(v,false,sizeof(v));
		v[x] = true;
		dfs(x,y);//计算各边权值 
	}
	for(int i=n-1;i>0;i--){//倒序去找到满足条件的第一条边一定是最大的 
		if(w[i]==m){//能够满足要求的边一定是每组数据都要经过的公共边 
			cout<<i;
			break;
		}
	}
}
int main(){
	solve();
	return 0;
}

用树链剖分+树差分优化后：

#includeusing namespace std;
typedef pair pii;
const int N = 1e5+10;
map id;
vectore[N];//存图
int n,m;

//树链剖分：
int fa[N],son[N],sz[N];//fa[u]存u的父节点，son[u]u的重儿子，sz[u]u为根节点的子树节点数(包括自己) 
int top[N],dep[N];//top[u]指u所在的重链顶点(是一个轻儿子节点)   dep[u]u所在的层级 

//初始化为0

void dfs1(int u,int father){//完善 fa[],sz[],dep[],son[] 
	fa[u] = father,dep[u] = dep[father] + 1,sz[u] = 1;//sz[u] = 1自己 
	for(int v : e[u]){
		if(v==father) continue;
		dfs1(v,u);
		sz[u] += sz[v];//节点大小加上子节点的大小 
		if(sz[son[u]] < sz[v]) son[u] = v;
	}	
} 

//初始调用dfs2(1,1) 
void dfs2(int u,int t){//完善top[] 
	top[u] = t;
	if(!son[u]) return ;//没有重儿子就返回
	dfs2(son[u],t);//如果有重儿子就深入遍历 连接这一条重儿子链top都为t
	for(int v : e[u]) {
		if(v==fa[u] || v==son[u]) continue;//重儿子和父节点不在遍历
		dfs2(v,v);//轻儿子节点的top为他自己 
	}
}

int lca(int u,int v){//找两个节点的最小公共祖先 
	while(top[u]!=top[v]){//u,v节点不在一条重链上 
		if(dep[top[u]] < dep[top[v]]) swap(u,v);//让u始终为重链顶点更深的那一方 
		u = fa[top[u]] ;//u向上跳 
	} 
	return dep[u] < dep[v] ? u : v;//返回uv层次更低的那一方 
} 
//可能用到： 
int w[N];
void cal_w(int u){//w[i]表示边权 用他下面一个顶点的点权记录 
	for(int v : e[u]){
		if(v==fa[u]) continue;
		cal_w(v);
		w[u] += w[v];
	}	
	
}


void solve(){
	//数据初始化 
	memset(sz,0,sizeof(sz)); 
	memset(dep,0,sizeof(dep)); 
	memset(son,0,sizeof(son));
	memset(w,0,sizeof(w)); 
	cin>>n>>m;
	for(int i=1;i>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
		id[{x,y}] = id[{y,x}] = i;
	}
	
	dfs1(1,0);
	dfs2(1,1);
	
	
	for(int i=0;i>x>>y;
		//用到树差分的边差分：
		//对两点路径边的权值加1等价于两点权值加1，最小公共祖先-2
		//不详细介绍证明 
		w[x]++;w[y]++;
		w[lca(x,y)]-=2;
	}
	cal_w(1);//各边的权值 
	
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(w[i]==m){//满足条件的边权 
			int id_ = id[{i,fa[i]}];//用的点权记录边权，记录的是他和他父节点的之间的边权 
			ans = max(ans,id_);//边的编号最大 
		}
	}
	cout<<ans;
}
int main(){
	solve();
	return 0;
}