P3379 【模板】最近公共祖先（LCA） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

简单模板，过了无数遍

P3128 [USACO15DEC] Max Flow P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

树上差分

就差一点

#include<iostream>
using namespace std;
int  n,k;
int dep[50001];
int fa[50001][21];
int a[50001];
int b[50001];

struct EDGE{

int next;
int to;


}edge[100001];
int head[50001];
int tot=0;
void addedge(int u,int v){
edge[++tot].next=head[u];
edge[tot].to=v;
head[u]=tot;
}
void dfs(int u,int father){

dep[u]=dep[father]+1;
for(int i=1;(1<<i)<=dep[u];i++){
    fa[u][i]=fa[fa[u][i-1]][i-1];
}

for(int i=head[u];~i;i=edge[i].next){
    int v=edge[i].to;
    if(v==father)continue;
    fa[v][0]=u;
    dfs(v,u);
}

}

void dfss(int u,int father){


cout<<"现在u,fa"<<u<<" "
//a[u]=子树a+差分b
    a[u]=b[u];


for(int i=head[u];~i;i=edge[i].next){

    int v=edge[i].to;cout<<"现在v"<<v<<endl;
    if(v==father)continue;

    dfs(v,u);
    a[u]+=a[v];
    for(int i=1;i<=n;i++){

        cout<<a[i]<<" ";}
        cout<<endl;
}


}

int  lca(int x,int y){

if(dep[x]<dep[y])swap(x,y);

for(int i=20;i>=0;i--){
    if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
    if(x==y)return x;
}


for(int i=20;i>=0;i--){
    if(fa[x][i]!=fa[y][i]){
        x=fa[x][i];
        y=fa[y][i];
    }
}


return fa[x][0];

}

int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)head[i]=-1;

for(int i=1;i<=n-1;i++){
    int u,v;
    cin>>u>>v;
    addedge(u,v);
    addedge(v,u);
}

dfs(1,0);




while(k--){
int x,y;
cin>>x>>y;
int mf=lca(x,y);


b[x]++;
b[y]++;
b[mf]--;
if(mf != 1) b[fa[mf][0]]--;

}







cout<<"现在检验5的边";
for(int i=head[5];~i;i=edge[i].next)
{
cout<<edge[i].to<<" ";

}
cout<<"检验结束"<<endl;

dfss(1,0);
int ans=0;



for(int i=1;i<=n;i++){



ans=max(ans,a[i]);
}

cout<<ans;

}

P5002 专心OI - 找祖先 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

n^3 tle