P3128 [USACO15DEC] Max Flow P [나무 에 차이 점 포인트 차이 점 (LCA)]

2955 단어 #LCA데이터 구조
P3128 [USACO15DEC]Max Flow P
 제목
  • 한 개의 나무, 나무 에 있 는 모든 노드 초기 화 점 권 은 0. k 번 조작 이 있 고 매번 조작 할 때마다 경로 에 있 는 모든 노드 에 1 번 조작 을 합 니 다.― k 차 조작 이 모두 완 료 된 후, 점 가중치 가 가장 큰 결점 의 점 권 은 얼마 입 니까?

    • 사고의 방향
  • 트 리 의 차이 점 템 플 릿
  • 뿌리 없 는 나무 에서 뿌리 있 는 나무 로
  • 경로 조작 시 + + sum [u], + sum [v], -- sum [lca (u, v)], -- sum [fa [lca (u, v)] [즉 차분 조작]
  •  dfs 전체 나무, 어떤 결점 의 점 권 은 이 결점 을 뿌리 로 하 는 자나무 의 차이 점 과 같다. 
  • 변 차 점: ++sum[u], ++sum[v], sum[lca(u, v)] -= 2
  • dfs 가 완 주 한 후에 sum [u] 는 결점 u 에서 그의 아버지 결점 까지 의 변 권
    • 이다.
    트 리 차이 점 참조 블 로그
    #include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
using namespace std;

typedef long long ll;

inline int read()
{
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int maxN = 50004; //    

int n, k;

struct EDGE{
    int adj, to;
    EDGE(int a = -1, int b = 0): adj(a), to(b) {}
}edge[maxN << 1];
int head[maxN], cnt;

void add_edge(int u, int v)
{
    edge[cnt] = EDGE(head[u], v);
    head[u] = cnt ++;
}

int f[maxN][20], deep[maxN];

void dfs(int u, int fa)
{
    deep[u] = deep[fa] + 1;
    f[u][0] = fa;
    for(int i = head[u]; ~i; i = edge[i].adj)
    {
        int v = edge[i].to;
        if(v == fa) continue;
        dfs(v, u);
    }
}

void pre()
{
    dfs(1, 0);
    for(int i = 1; i < 20; ++ i )
        for(int j = 1; j <= n; ++ j )
            f[j][i] = f[f[j][i - 1]][i - 1];
}

int LCA(int u, int v)
{
    if(deep[u] < deep[v]) swap(u, v);
    for(int i = 19; i >= 0; -- i )
    {
        if(deep[f[u][i]] >= deep[v])
            u = f[u][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; -- i )
    {
        if(f[u][i] != f[v][i])
        {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}

int sum[maxN], ans;

void getAns(int u, int fa)
{
    for(int i = head[u]; ~i; i = edge[i].adj)
    {
        int v = edge[i].to;
        if(v == fa) continue;
        getAns(v, u);
        sum[u] += sum[v];
    }
    ans = max(ans, sum[u]);
}

int main()
{
    memset(head, -1, sizeof(head));
    n = read(); k = read();
    for(int i = 0; i < n - 1; ++ i )
    {
        int u, v; u = read(); v = read();
        add_edge(u, v);
        add_edge(v, u);
    }
    pre();
    for(int i = 0; i < k; ++ i )
    {
        int u, v; u = read(); v = read();
        int lca = LCA(u, v), fa = f[lca][0];
        ++ sum[u]; ++ sum[v];
        -- sum[lca]; -- sum[fa];
    }
    getAns(1, 0);
    printf("%d
    ", ans);
    return 0;
}

    QAQ, 바가지!오입질 을 하 다.  1 조 테스트 샘플 이 제 시 된 샘플 인 줄 몰랐어 요. QAQ.
    Kite를 사용하여 JupyterLab에 Autocomplete 가져오기
    AngularJs 동적 로드 모듈 및 종속 주입 상세 정보

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage