网站开发需求说明,网站3d特效源码,网站被做跳转怎么办,设计购物网站咋做题面 FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道#xff0c;隔间编号从1到N。所有隔间都被管道连通了。 FJ有K(1≤K≤100,000)条运输牛奶的路线#xff0c;第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个…题面 FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道隔间编号从1到N。所有隔间都被管道连通了。 FJ有K(1≤K≤100,000)条运输牛奶的路线第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力你需要计算压力最大的隔间的压力是多少。 分析 树上点差分模板。 代码 #includebits/stdc.h using namespace std; #define N 500050 int n,m,cnt,ans; int c[N],fa[N][20],dep[N],first[N]; struct email { int u,v; int nxt; }e[N*4]; templateclass T inline void read(T x) { x0;int f1;static char cgetchar(); while(c0||c9) {if(c-)f-1;cgetchar();} while(c0c9){xx*10c-0,cgetchar();} x*f; } inline void add(int u,int v) { e[cnt].nxtfirst[u];first[u]cnt; e[cnt].uu;e[cnt].vv; } inline void pre(int u,int f) { for(int i1;(1i)dep[u];i) fa[u][i]fa[fa[u][i-1]][i-1]; for(int ifirst[u];i;ie[i].nxt) { int ve[i].v; if(vf)continue; dep[v]dep[u]1; fa[v][0]u; pre(v,u); } } inline int lca(int x,int y) { if(dep[x]dep[y])swap(x,y); int tdep[x]-dep[y]; for(int i0;(1i)t;i) if((1i)t) xfa[x][i]; if(xy)return x; for(int i19;i0;i--) if(fa[x][i]!fa[y][i]) xfa[x][i],yfa[y][i]; return fa[x][0]; } inline void dfs(int u,int f) { for(int ifirst[u];i;ie[i].nxt) { int ve[i].v; if(vf)continue; dfs(v,u); c[u]c[v]; } ansmax(ans,c[u]); } int main() { read(n),read(m); for(int i1;in;i) { int u,v; read(u),read(v); add(u,v);add(v,u); } pre(1,0); for(int i1;im;i) { int s,t; read(s),read(t); c[s],c[t],c[lca(s,t)]--,c[fa[lca(s,t)][0]]--; } dfs(1,0); printf(%d\n,ans); return 0; } 转载于:https://www.cnblogs.com/NSD-email0820/p/9853237.html
