做网站需要注册商标第几类,公司域名邮箱怎么注册,网站建设方案word,数据库能上传网站模板正题 题目大意
一棵树 若干条路径#xff0c;哪个点经过的路径最多#xff0c;求路径条数。 解题思路
对于每条路径计算一次LCALCALCA#xff0c;然后树上差分就好了。 codecodecode
#includecstdio
#includequeue
#includecmath
using namespac…正题 题目大意
一棵树 若干条路径哪个点经过的路径最多求路径条数。 解题思路
对于每条路径计算一次LCALCALCA然后树上差分就好了。 codecodecode
#includecstdio
#includequeue
#includecmath
using namespace std;
const int N50010;
struct node{int to,next;
}a[N*2];
int tot,ls[N],dep[N],f[N][20],c[N];
int y,n,k,t,ans;
queueint q;
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void bfs()
{t(int)(log(n)/log(2))1;q.push(1);dep[1]1;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[y]) continue;dep[y]dep[x]1;f[y][0]x;q.push(y);}}for(int j1;jt;j)for(int i1;in;i)f[i][j]f[f[i][j-1]][j-1];
}
int LCA(int x,int y)
{if(dep[x]dep[y]) swap(x,y);for(int it;i0;i--)if(dep[f[y][i]]dep[x])yf[y][i];if(xy) return x;for(int it;i0;i--)if(f[y][i]!f[x][i]){yf[y][i];xf[x][i];}return f[x][0];
}
void get_ans(int x)
{for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[x]1!dep[y]) continue;get_ans(y);c[x]c[y];}ansmax(ans,c[x]);
}
int main()
{scanf(%d%d,n,k);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}bfs();for(int i1;ik;i){int s,e,lca;scanf(%d%d,s,e);lcaLCA(s,e);c[s];c[e];c[lca]--;c[f[lca][0]]--;}get_ans(1);printf(%d,ans);
}
