树剖求LCA+树上差分TLE求助
查看原帖
树剖求LCA+树上差分TLE求助
136362
Moonsfrost楼主2020/8/2 20:32

RT

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<cctype>
#include<vector>
#define ll long long
using namespace std;
inline int read(){
	int f=1,num=0;
	char rd=getchar();
	while(!isdigit(rd)){
		if(rd=='-') f=-1;
		rd=getchar();
	}
	while(isdigit(rd)){
		num=num*10+rd-48;
		rd=getchar();
	}
	return f*num;
}
#define MAXN 50020
int head[MAXN],to[MAXN<<1],next[MAXN<<1],cnt;
void add(int x,int y){
    next[++cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
}
int a[MAXN],fa[MAXN],son[MAXN],top[MAXN],size[MAXN],d[MAXN];
void dfs1(int x,int f){
    d[x]=d[f]+1;
    fa[x]=f;
    for(int i=head[x];i;i=next[i]){
        if(to[i]==f) continue;
        dfs1(to[i],x);
        size[x]+=size[to[i]];
        son[x]=size[son[x]]>size[to[i]]?son[x]:to[i];
    }
}
void dfs2(int x,int f){
    if(x==son[f]) top[x]=top[f];
    else top[x]=x;
    if(son[x]) dfs2(son[x],x);
    for(int i=head[x];i;i=next[i]){
        if(to[i]==son[x]||to[i]==f) continue;
        dfs2(to[i],x);
    }
}
void lca(int x,int y){
    a[x]++,a[y]++;
    while(top[x]!=top[y]){
        if(d[top[x]]>d[top[y]]) swap(x,y);
        y=fa[top[y]];
    }
    if(d[x]>d[y]) swap(x,y);
    a[x]--,a[fa[x]]--;
}

int maxn;
int dfs3(int x,int f){
    int now=a[x];
    for(int i=head[x];i;i=next[i]){
        if(to[i]==f) continue;
        now+=dfs3(to[i],x);
    }
    maxn=max(maxn,now);
    return now;
}

int main()
{
    int n=read(),T=read(),x,y;
    for(int i=1;i<n;i++){
        x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    dfs1(n,0),dfs2(n,0);
    while(T--) lca(read(),read());
    dfs3(n,0);
    return printf("%d\n",maxn)&0;
}

2020/8/2 20:32
加载中...