差分

boke

最大流

#include<bits/stdc++.h>
#define re return
#define st static
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;--i)
#define lowbit(x) (x&(-x))

template<typename T>inline void read(T&x)
{
	char c;bool f=0;
	while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
	x=c^48;
	while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
	if(f)x=-x;
}

using namespace std;

int n,m,k,b,head[50005],deep[50005],fa[50005][30],dis[50005],maxx;
//fa数组越界 

struct node
{
	int to,nt,val;
}e[100005];

void add(int x=0,int y=0)
{
	read(x),read(y);
	e[++k].to=y;e[k].nt=head[x];head[x]=k;
	e[++k].to=x;e[k].nt=head[y];head[y]=k;
}

void dfs(int x)
{
	deep[x]=deep[fa[x][0]]+1;
//	for(int i=0;fa[x][i];++i)fa[x][i+1]=fa[fa[x][i]][i];
	for(int i=head[x];i;i=e[i].nt)
	{
		int v=e[i].to;
		if(v!=fa[x][0])
		{
			fa[v][0]=x;
			dfs(v);
		}
	}
}

int ask(int u,int v)
{
	if(deep[u]<deep[v])	u^=v^=u^=v;
	dec(i,20,0)
	if(deep[fa[u][i]]>=deep[v])
		u=fa[u][i];
	
	if(u==v)re u;
	
	dec(i,20,0)
	//dec&&inc
	if(fa[u][i]!=fa[v][i])  
	u=fa[u][i],v=fa[v][i];
	
	re fa[u][0];
}

void dfsv(int x)
{
	for(int i=head[x];i;i=e[i].nt)
	{
		int v=e[i].to;
		if(v!=fa[x][0])
		{
			dfsv(v);
			dis[x]+=dis[v];
		}
	}
	maxx=max(dis[x],maxx);
}

int main()
{	
	int x,y;

	freopen("in.txt","r",stdin);
	read(n),read(m);
	inc(i,2,n)add();
	
	
	dfs(1);
//	b=(log(maxx)/log(2));
	
	inc(j,1,20)
	inc(i,1,n)
	if(fa[i][j-1])
	fa[i][j]=fa[fa[i][j-1]][j-1];
	
	inc(i,1,m)
	{
		read(x),read(y);
		int lca=ask(x,y);
		++dis[x];++dis[y];--dis[lca];--dis[fa[lca][0]];
	}
	
	maxx=0;
	dfsv(1);

	cout<<maxx;
 	re 0;
}

P3258 [JLOI2014]松鼠的新家

#include<bits/stdc++.h>
#define re return
#define st static
#define inc(i,l,r) for(int i=l;i<=r;++i)
#define dec(i,l,r) for(int i=l;i>=r;--i)
const int maxn=3000005,maxm=6000005;

template<typename T>inline void read(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')c=getchar();
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}

using namespace std;
int n,m,k,head[maxn],d[maxn],dep[maxn],a[maxn],fa[maxn][30];

struct node
{
    int to,nt;
}e[maxm];

void add(int x=0,int y=0)
{
    read(x),read(y);
    e[++k].to=y;e[k].nt=head[x];head[x]=k;
    e[++k].to=x;e[k].nt=head[y];head[y]=k;
}

void dfs(int x)
{
    dep[x]=dep[fa[x][0]]+1;
    for(int i=0;fa[x][i];i++)fa[x][i+1]=fa[fa[x][i]][i];
    for(int i=head[x];i;i=e[i].nt)
    {
        int v=e[i].to;
        if(v!=fa[x][0])
        {
            fa[v][0]=x;
            dfs(v);
        }
    }
}

void dfsv(int x)
{
    for(int i=head[x];i;i=e[i].nt)
    {
        int v=e[i].to;
        if(v!=fa[x][0])
        {
            dfsv(v);
            d[x]+=d[v];
        }
    }
}

int LCA(int u,int v)
{
    if(dep[u]<dep[v])u^=v^=u^=v;
    dec(i,20,0)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
    
    if(u==v) re u;
    
    dec(i,20,0)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    re fa[u][0];
}

int main()
{
/*	freopen("testdata(2).in","r",stdin);
    freopen("out.txt","w",stdout);*/
    read(n);
    inc(i,1,n)read(a[i]);
    inc(i,2,n)add();
    
    dfs(1);
    
    inc(i,1,n-1)
    {
        int lca=LCA(a[i],a[i+1]);
        ++d[a[i]],++d[a[i+1]],--d[lca],--d[fa[lca][0]];
    }
    
    dfsv(1);
    
    d[a[1]]++;
    
    inc(i,1,n)printf("%d\n",d[i]-1);
    re 0;
}

---

2680 运输计划

#include<bits/stdc++.h>
#define inc(i,l,r) for(int i=l;i<=r;++i)
#define reg register
#define re 	return

using namespace std;
const int maxn=300005,maxm=600005;

template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48);
    if(f)x=-x;
}
int n,m,k,k1,l,r,num,res,maxlen;
int to[maxm],nt[maxm],to1[maxm],val[maxm],nt1[maxm],head1[maxm],dis[maxn],head[maxn],faa[maxn],vis[maxn],cnt[maxn],a[maxn];


struct node
{
    int x,y,lca,dis;
}ask[maxn];

inline void add(int x=0,int y=0,int z=0)
{
    rd(x),rd(y),rd(z);
    to[++k]=y;nt[k]=head[x];val[k]=z;head[x]=k;
    to[++k]=x;nt[k]=head[y];val[k]=z;head[y]=k;
    r+=z;
}

inline void add1(int x,int y)
{
    nt1[++k1]=head1[x];head1[x]=k1;to1[k1]=y;
    nt1[++k1]=head1[y];head1[y]=k1;to1[k1]=x;
}
//-----------------------------------------tarjan------------------------------------------------//
inline int find(int x){re x==faa[x]?x:faa[x]=find(faa[x]);	}
//最近公共祖先
void tarjan(int u,int fa)
{
    for(int i=head[u];i;i=nt[i])
    {
        int v=to[i],w=dis[u]+val[i];
        if(v==fa)continue;
        dis[v]=w;
        a[v]=w-dis[u];
        //将边塞到点上
        tarjan(v,u);
        int f1=find(v);
        int f2=find(u);
        if(f1!=f2)
            faa[f1]=find(f2);
        vis[v]=1;
    }
    
    for(int i=head1[u];i;i=nt1[i])
    {
        int v=to1[i];
        if(vis[v])
        {
            int now=(i+1)>>1;
            ask[now].lca=find(faa[v]);
            ask[now].dis=dis[v]+dis[u]-(dis[ask[now].lca]<<1);
            maxlen=max(ask[now].dis,maxlen);
        }
    }
}
//--------------------------------------------差分-----------------------------------------------//

void dfvv(int u,int fa)
{
    for(int i=head[u];i;i=nt[i])
    {
        int v=to[i];
        if(v!=fa)
        {
            dfvv(v,u);
            cnt[u]+=cnt[v];
        }
    }
    if(cnt[u]==num&&a[u]>res)res=a[u];	
} //统计

 inline bool check(int x)
 {
 	memset(cnt,0,sizeof(cnt));
 	
 	res=num=0;
 	for(int i=1;i<=m;i++)
 	if(ask[i].dis>x) cnt[ask[i].x]++,cnt[ask[i].y]++,cnt[ask[i].lca]-=2,num++;
 	//边塞点lca-2；
    
    dfvv(1,0);
    
 	re maxlen-res<=x;
 }
//--------------------------------------------main-----------------------------------------------//
int main()
{	
    //freopen("testdata(2).in","r",stdin);
    //	freopen("in.txt","r",stdin);
    
    rd(n),rd(m);
    inc(i,2,n)add();
    inc(i,1,m){
        rd(ask[i].x),rd(ask[i].y);
        add1(ask[i].x,ask[i].y);
    }
    
    inc(i,1,n)faa[i]=i;
    tarjan(1,0);
    
    while(l<=r)//二分一波，最大值最小
    {
        int mid=(l+r)>>1;
        if(check(mid))r=mid-1;
        else l=mid+1;
    }
    
    printf("%d",l);
    re 0;
}