题目描述
砍树
样例
略
算法1
(暴力DFS) $O(n^2)$
无环连通图,进行DFS搜索能从起点到达终点的路径,并通过存储边权,来最后输出边权为m路径的边的编号,只要去除公共边就能使其不连通。
C++ 代码
//暴力做法
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int>pii;
const int N=2e5+10;
int w[N];//存储边遍历的次数
map<pii,int>id;//存储每条边的id
vector<int>edge[N];//存储图
bool DFS(int s,int u,int father,int v)//初始点、当前点、父节点、终点
{
if(u==v)//当前点==终点
{
return true;
}
for(int i=0;i<edge[u].size();i++)//遍历当前点的所有儿子节点
{
if(edge[u][i]==father)//防止重复
{
continue;
}
if(DFS(s,edge[u][i],u,v))//该条边能到达终点
{
w[id[{u,edge[u][i]}]]++;//对应的父亲到儿子这条边+1
//w[id[{edge[u][i],u}]]++;
//cout<<w[id[{u,edge[u][i]}]]<<endl;
return true;
}
}
return false;//找不到能到终点的边
}
void solve()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n-1;i++)
{
int x,y;
cin>>x>>y;
edge[x].push_back(y);//初始化无环连通图
edge[y].push_back(x);
id[{x,y}]=i+1;//对应的边号
id[{y,x}]=i+1;
}
for(int i=0;i<m;i++)//需要dfs的m条路经
{
int x,y;
cin>>x>>y;
DFS(x,x,-1,y);//找这m条路经的公共边
}
for(int i=n-2;i>=0;i--)//从大到小遍历编号
{
//cout<<w[i+1];
if(w[i+1]==m)//边的权值等于m
{
cout<<i+1;
break;
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
算法2
(树上差分+最近公共祖先)
第一步:给路径的起点和终点都+1
第二步:给两个点的lca-2
所有差分做完之后
第三步:让每个点都加上它的子树和
最后,点权等于这个点和他父节点相连的边的边权。
C++ 代码
//树上差分+最近公共祖先
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int>pii;
const int N=2e5+10;
int w[N];//存储点权
map<pii,int>id;//存储每条边的id
vector<int>edge[N];//存储图
int fa[N],siz[N],son[N],top[N],dep[N];//最近公共祖先模板
void dfs1(int u,int father)
{
fa[u]=father;dep[u]=dep[father]+1;siz[u]=1;
for(int i=0;i<edge[u].size();i++)
{
if(edge[u][i]==father)
{
continue;
}
dfs1(edge[u][i],u);
siz[u]+=siz[edge[u][i]];
if(siz[son[u]]<siz[edge[u][i]])son[u]=edge[u][i];
}
}
void dfs2(int u,int t)
{
top[u]=t;
if(!son[u])return ;
dfs2(son[u],t);
for(int i=0;i<edge[u].size();i++)
{
int v=edge[u][i];
if(v==fa[u]||v==son[u])
continue;
dfs2(v,v);
}
}
int lca(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
//树上前缀和,点权之和
void cal_sum(int u,int father)
{
for(int i=0;i<edge[u].size();i++)
{
int v=edge[u][i];
if(v==father)
continue;
cal_sum(v,u);
w[u]+=w[v];
}
}
void solve()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n-1;i++)
{
int x,y;
cin>>x>>y;
edge[x].push_back(y);//初始化无环连通图
edge[y].push_back(x);
id[{x,y}]=i+1;//对应的边号
id[{y,x}]=i+1;
}
dfs1(1,0);
dfs2(1,1);
for(int i=0;i<m;i++)//树上差分
{
int x,y;
cin>>x>>y;
w[x]++;w[y]++;//起点终点+1
w[lca(x,y)]-=2;//最近公共祖先-2
}
cal_sum(1,0);
int ans=-1;
for(int i=1;i<=n;i++)//从小到大遍历编号
{
//cout<<w[i+1];
if(w[i]==m)//点的权值等于m
{
int idd=id[{i,fa[i]}];//映射到边权
ans=max(ans,idd);//取编号最大
}
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}