알고리즘 경연 진급 안내 dp 학습 노트--Day2

구간DP

구간 길이를 단계로 하고 구간 좌우 단점을 상태의 일종인 DP는 그 하위 문제와 원 문제가 라인 트리와 같은 구조를 구성한다
[스톤 합병] 이거 너무 고전적이야...다시 하고 싶지 않아요.
[Polygon] 배로 늘리고 돌을 합쳐서.
【Exploring Pyramids】
트리의 하위 트리와 문자열의 구간을 연결합니다
단계:구간 길이
상태:구간 좌우 끝점
결정: 서브트리가 차지하는 구간을 선택하여 분류 덧셈과 단계 곱셈 원리를 이용하여 통계 답안을 작성한다.
 

트리 DP

나무에 dp를 만들면 보통 나무의 깊이를 단계로 한다
[상사 없는 무도회] 역시 명작이죠.
【수강신청】 나무 위 가방과 가상 소스
【Accumulation Degree】
Description
뿌리 없는 나무 한 그루를 정하고 한 변에 유량 상한선이 있으며 한 점을 원점으로 지정하고 무한한 물이 있다.
나무에서 이 점을 제외한 다른 도수가 1인 점은 합류점이고 전체 수계의 유량은 각 합류점을 통과하는 최대 유량의 합으로 정의된다
어느 점을 원점으로 할 때 전체 수계의 유량이 가장 크면 이 최대치를 출력한다.
포인트<=2e5
Sol
소박한 방법: 임의의 점을 뿌리로 dp 총계 답안을 한 번 만들고 복잡도 O(n2)
소박한 방법에서 통계 답안을 반복하는 것을 발견하여 기억화 검색을 고려하고 d[i][j]를 저장하면 j가 i를 부모 노드로 할 때의 최대 데이터를 나타낸다
하지만 아래를 내려다보니 리드 대장의 nb 방법은 두 번만 뒤져봐...

2차 스캐닝과 루트 교환법

 1 . 처음 스캔할 때 점 중 하나를 루트로 선택하고 루트 트리에서 트리 DP를 실행합니다.
거슬러 올라갈 때 발생하는, 밑에서 위로 이동하는 상태
 2 . 두 번째 스캔을 할 때, 방금 선택한 뿌리에서 출발하여, 나무 전체에 깊이를 우선적으로 반복합니다.
귀속 전에 위에서 아래로 유도하여'뿌리갈이'후의 해를 계산해 내다
(알고리즘 경연 진급 안내서에서 발췌)
이 문제에 적용하면 1을 루트 DP로 한 번에 각 노드의 최대 유량을 계산한다
다시 한 번 1에서 아래로 깊이 뒤져 한 시가 되면 뿌리가 되고, 답은 아버지의 그 나무에 기여한다(수색할 때 계산하고 아래로 가져간다)
기존에 계산한 그것의 유량을 더하다
Code
 

#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
const int N=2e5+10;
struct node
{
    int v;
    ll w;
};
vector  link[N];
int n,T,u,v;
ll w,f[N],ans;
void dfs1(int u,int fa,ll w)
{
    f[u]=0;
    int size=link[u].size();
    bool flag=false;
    for(int i=0;i)
    {
        node t=link[u][i];
        if(t.v==fa) continue;
        dfs1(t.v,u,t.w),flag=true;
        f[u]+=min(t.w,f[t.v]);
    }
    if(!flag) f[u]=w;
}
void dfs2(int u,int fa,ll res)
{
    ans=max(ans,f[u]+res);
    int size=link[u].size();
    for(int i=0;i)
    {
        node t=link[u][i];
        if(t.v==fa) continue;
        dfs2(t.v,u,min(t.w,res+f[u]-min(t.w,f[t.v])));
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) link[i].clear();
        for(int i=1;i)
        {
            scanf("%d%d%lld",&u,&v,&w);
            link[u].push_back((node){v,w});
            link[v].push_back((node){u,w});
        }
        dfs1(1,0,1<<30);
        ans=0;
        dfs2(1,0,0);
        printf("%lld
",ans);
    }
    return 0;
}