백준 12745 - Traffic (Small)

문제링크 : https://www.acmicpc.net/problem/12745

오일러경로테크닉 + LCA + 레이지 세그(근데 어차피 리프노드까지가서 update하므로.. 필요가없다....)

정리는 내일하자...
플래4가 아닌거같다........................
내가 괜히 어렵게한건지 .. . .

태그에 누적합이있는데 비선형구조인 그래프에서 간선을 어케
처리해줘야 하는지 모르것다.. 내일 남들어떻게 풀었는지좀 봐야겟다

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;
int N,M;
vector<int> v[2223];
int in[2223],out[2223],idx;
int level[2223],p[2223][21];
long long segtree[2223*4],lazy[2223*4];
void dfs(int now,int parent){
    in[now]=idx++;
    for(int child : v[now]){
        if(child == parent) continue;
        dfs(child,now);
    }
    out[now]=idx-1;
}
void set_tree(int node,int pnode,int lv){
    level[node]=lv;
    p[node][0]=pnode;
    for(int i=1;i<=20;i++){
        p[node][i]=p[p[node][i-1]][i-1];
    }
    for(int child : v[node]){
        if(child == pnode) continue;
        set_tree(child,node,lv+1);
    }
}
void lazy_update(int s,int e,int node){
    if(lazy[node]){
        segtree[node]+=(e-s+1)*lazy[node];
        if(s!=e){
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
    }
}
void update(int s,int e,int node,int idx,int diff){
    lazy_update(s,e,node);
    if(idx<s||e<idx) return;
    if(s==e){
        segtree[node]+=(e-s+1)*diff;
        if(s!=e){
            lazy[node*2]+=diff;
            lazy[node*2+1]+=diff;
        }
        return ;
    }
    int mid = (s+e)/2;
    update(s,mid,node*2,idx,diff);
    update(mid+1,e,node*2+1,idx,diff);
    segtree[node]=segtree[node*2]+segtree[node*2+1];
}
int lca(int a,int b){
    if(a==1||b==1) return 1;
    if(level[a]<level[b]) swap(a,b);
    if(level[a]!=level[b]){
        for(int i=20;i>=0;i--){
            if(level[p[a][i]]>=level[b]){
                a=p[a][i];
            }
        }
    }
    int ret = a;
    if(a!=b){
        for(int i=20;i>=0;i--){
            if(p[a][i]!=p[b][i]){
                a=p[a][i];
                b=p[b][i];
            }
            ret = p[a][i];
        }
    }
    return ret;
}
long long query(int s,int e,int node,int l,int r){
    lazy_update(s,e,node);
    if(l>e||r<s) return 0;
    if(l<=s&&e<=r) return segtree[node];
    int mid = (s+e)/2;
    return query(s,mid,node*2,l,r)+query(mid+1,e,node*2+1,l,r);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>N>>M;
    vector<pair<int,int>> g;
    for(int i=0;i<N-1;i++){
        int a,b;cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        g.push_back({a,b});
    }
    set_tree(1,0,1);
    dfs(1,0);
    for(int i=0;i<M;i++){
        int b,c;cin>>b>>c;
        int pnode = lca(b,c);
        update(0,N-1,1,in[pnode],-2);
        update(0,N-1,1,in[b],1);
        update(0,N-1,1,in[c],1);
    }
    int s,e,ans=0;
    for(int i=0;i<g.size();i++){
        int a=g[i].first;int b = g[i].second;
        int q = in[a]<in[b]?q=b:q=a;
        int temp = query(0,N-1,1,in[q],out[q]);
        if(ans<temp){
            s = min(a,b); e = max(a,b);
            ans=temp;
        }
    }
    cout<<s<<" "<<e<<" "<<ans;
}