Max Flow P

题意

给定一棵树，一些路径，一条路径上所有点权值$+1$，求权值最大的点权值

1 正解

考虑差分 一条路径$u\leftrightarrow v$分成$u\leftrightarrow lca$与$v\leftrightarrow lca$两部分 最终DFS

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0;bool f=true;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f^=1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return f?i:-i; } const int N=1e5+5; int n,k,f[N][20],deg[N],sum[N],ans; vector<int>G[N]; void DFS(int u,int fa){ deg[u]=deg[fa]+1; f[u][0]=fa; for(int v:G[u]){ if(v==fa) continue; DFS(v,u); } return; } int LCA(int u,int v){ if(deg[u]<deg[v]) swap(u,v); for(int i=16;i>=0;--i) if(deg[f[u][i]]>=deg[v]) u=f[u][i]; if(u==v) return u; for(int i=16;i>=0;--i) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i]; return f[u][0]; } void get(int u,int fa){ for(int v:G[u]){ if(v==fa) continue; get(v,u); sum[u]+=sum[v]; } ans=max(ans,sum[u]); return; } int main(){ n=in,k=in; for(int i=1;i<n;++i){ int u=in,v=in; G[u].push_back(v); G[v].push_back(u); } DFS(1,0); for(int l=1;l<=16;++l) for(int u=1;u<=n;++u) f[u][l]=f[f[u][l-1]][l-1]; for(int i=1;i<=k;++i){ int u=in,v=in,lca=LCA(u,v); ++sum[u]; ++sum[v]; --sum[lca]; --sum[f[lca][0]]; } get(1,0); printf("%d\n",ans); return 0; }

以前用树剖做的 复习一下树剖

#include<bits/stdc++.h> #define in Read() #define lch p<<1 #define rch p<<1|1 #define int long long using namespace std; inline int in{ int i=0,f=1;char ch; while(!isdigit(ch)&&ch!='-')ch=getchar(); if(ch=='-')ch=getchar(),f=-1; while(isdigit(ch))i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } const int NNN=1e5+10; int n,m; int first[NNN],nxt[NNN<<1],aim[NNN],etot; int fat[NNN],son[NNN],top[NNN],siz[NNN],dfn[NNN],dep[NNN],tot; struct Tree{ int val,l,r,laz; }tr[NNN<<2]; inline void add(int u,int v){ nxt[++etot]=first[u]; first[u]=etot; aim[etot]=v; return; } inline void DFS1(int fa,int u){ fat[u]=fa,siz[u]=1,dep[u]=dep[fa]+1; for(int e=first[u];e;e=nxt[e]){ int v=aim[e]; if(v==fa) continue; DFS1(u,v); siz[u]+=siz[v]; if(siz[son[u]]<siz[v]) son[u]=v; } return; } inline void DFS2(int u,int pik){ top[u]=pik,dfn[u]=++tot; if(!son[u]) return; DFS2(son[u],pik); for(int e=first[u];e;e=nxt[e]){ int v=aim[e]; if(v==son[u]||v==fat[u]) continue; DFS2(v,v); } return; } inline void push_up(int p){ tr[p].val=max(tr[lch].val,tr[rch].val); return; } inline void push_down(int p){ if(!tr[p].laz) return; tr[lch].laz+=tr[p].laz; tr[rch].laz+=tr[p].laz; tr[lch].val+=tr[p].laz; tr[rch].val+=tr[p].laz; tr[p].laz=0; return; } inline void build(int p,int l,int r){ tr[p].l=l,tr[p].r=r; if(l==r) return; int mid=(l+r)>>1; build(lch,l,mid); build(rch,mid+1,r); return; } inline void update(int p,int l,int r){ if(l<=tr[p].l&&tr[p].r<=r){ ++tr[p].val; ++tr[p].laz; return; } push_down(p); int mid=(tr[p].l+tr[p].r)>>1; if(l<=mid) update(lch,l,r); if(r>mid) update(rch,l,r); push_up(p); return; } inline void Modify(int u,int v){ while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); update(1,dfn[top[u]],dfn[u]); u=fat[top[u]]; } if(dep[u]>dep[v]) swap(u,v); update(1,dfn[u],dfn[v]); return; } signed main(){ n=in,m=in; for(int i=2;i<=n;++i){ int u=in,v=in; add(u,v),add(v,u); } DFS1(0,1); DFS2(1,1); build(1,1,n); for(int i=1;i<=m;++i) Modify(in,in); printf("%lld\n",tr[1].val); return 0; }