麻涌镇网站仿做,logo设计大师,群晖wordpress 外网,外包公司一个人头挣多少钱题面 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
