大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
意甲冠军:它使树m路径,当被问及选择尽可能多的路径,而这些路径不相交。
思考:贪心,比較忧伤。首先求一下每对路径的lca。依照lca的层数排序。在深一层的优先级高。那么就能够贪心了,每次选择层数最深的那一个,假设两个端点没有被标记,那么就选择这条路径,把lca的子树都标记掉。
代码:
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<map> #include<queue> #include<stack> #include<set> #include<cmath> #include<vector> #define inf 0x3f3f3f3f #define Inf 0x3FFFFFFFFFFFFFFFLL #define eps 1e-9 #define pi acos(-1.0) using namespace std; typedef long long ll; const int maxn=100000+10; struct Edge { int v,next; Edge(int v=0,int next=0):v(v),next(next){} }edges[maxn<<1]; struct Node { int u,v,id; Node(int u=0,int v=0,int id=0):u(u),v(v),id(id) {} }node[maxn]; int head[maxn],nEdge; int LCA[maxn],pa[maxn],d[maxn]; bool vis[maxn]; vector<pair<int,int> >querys[maxn]; int Find(int x) { return x==pa[x]?x:pa[x]=Find(pa[x]); } void AddEdges(int u,int v) { edges[++nEdge]=Edge(v,head[u]); head[u]=nEdge; edges[++nEdge]=Edge(u,head[v]); head[v]=nEdge; } void dfs(int u,int fa) { pa[u]=u; pair<int,int>pii; for(int i=0;i<(int)querys[u].size();++i) { pii=querys[u][i]; if(d[pii.first]==-1) continue; LCA[pii.second]=Find(pii.first); } for(int k=head[u];k!=-1;k=edges[k].next) { int v=edges[k].v; if(v==fa) continue; d[v]=d[u]+1; dfs(v,u); pa[v]=u; } } bool cmp(Node a,Node b) { int u=LCA[a.id]; int v=LCA[b.id]; return d[u]>d[v]; } void Init(int n) { memset(vis,0,sizeof(vis)); memset(head,0xff,sizeof(head)); nEdge=-1; memset(d,0xff,sizeof(d)); for(int i=0;i<=n;++i) querys[i].clear(); } void tour(int u) { vis[u]=true; for(int k=head[u];k!=-1;k=edges[k].next) { int v=edges[k].v; if(vis[v]||d[v]<d[u]) continue; tour(v); } } int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int n,m; while(~scanf("%d%d",&n,&m)) { Init(n); int u,v; for(int i=1;i<n;++i) { scanf("%d%d",&u,&v); AddEdges(u,v); } for(int i=0;i<m;++i) { scanf("%d%d",&u,&v); querys[u].push_back(make_pair(v,i)); querys[v].push_back(make_pair(u,i)); node[i].u=u;node[i].v=v; node[i].id=i; } d[1]=0; dfs(1,-1); sort(node,node+m,cmp); int cnt=0; for(int i=0;i<m;++i) { if(!vis[node[i].u]&&!vis[node[i].v]) { cnt++; tour(LCA[node[i].id]); } } printf("%d\n",cnt); } return 0; }
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117044.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...