【数据结构】树

最近公共祖先

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

简单模板，过了无数遍

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

6,wa tle

我想直接对区间暴力，应该也只是tle，但wa了

正解是树上差分，但没懂，也样例没过

#include<iostream>
using namespace std;
int  n,k;
int dep[50001];
int fa[50001][21];
int sum[50001];
int a[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){

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

    dfs(v,u);
    sum[u]=sum[v]+a[i];
}


}

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);


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









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

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

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

cout<<ans;

}

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

n^3 tle