2018.07.22 낙 곡 P3047 근처 소 (나무형 dp)

4997 단어 #상태 이동트 리 dp
전송 문 은 n 개의 점 의 나 무 를 주 고 점 마다 Ci C i 두 소 가 있 습 니 다. 점 마다 k 걸음 범위 내 에 소 가 몇 마리 있 는 지 물 어보 세 요.방금 문 제 를 보고 놀 라 서 이거 하면 안 되 는데.그리고 dp d p 를 바 꾸 려 고 했 는데 안 나 왔어요.계속 문 제 를 읽 어 보 니 k k 가 매우 작 구나. 겨우 20 밖 에 안 되 는데 이것 은 O (nk) O (n k) 를 뛸 수 있 는 알고리즘 이 아 닐 것 같다.그리고 O (nk) O (n k) 를 만 들 수 있다 는 것 을 알 게 되 었 습 니 다. 방법 은 이 렇 습 니 다.우 리 는 먼저 하나의 노드 (내 가 선택 한 것 이 1) 를 루트 노드 로 선택 한 다음 에 siz [p] [k] s i z [p] [k] [k] 로 각 p 를 루트 노드 로 하 는 서브 트 리 에서 p p p p 가 k k 보다 크 지 않 은 노드 의 가중치 와 서브 트 리 이외 의 노드 를 먼저 상관 하지 않 는 다 는 것 을 나타 낸다.이 물건 은 먼저 아들 의 정 보 를 통 해 각 p p 를 뿌리 노드 로 하 는 서브 트 리 에서 p p 는 k k 와 같은 노드 의 가중치 와 그 다음 에 접두사 와 구 할 수 있 습 니 다. 시간 복잡 도 O (nk) O (n k) 를 옮 긴 다음 에 모든 점 u 를 전체 나무의 뿌리 노드 로 할 때전체 나무의 공헌 은 u 에서 1 까지 의 사슬 을 따라 위로 뛰 거나 뛰 지 못 하거나 k 걸음 이 멈 추 었 을 때 간단 한 용 척 원리 로 답 을 집계 하 는 것 이다.코드 는 다음 과 같 습 니 다:
#include
#define N 100005
using namespace std;
int first[N],n,siz[N][21],cnt=0,dp[N],fa[N],k;
struct Node{int v,next;}e[N<<1];
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
inline void write(int x){
    if(x>9)write(x/10);
    putchar((x%10)^48);
}
inline void dfs(int p){
    for(int i=first[p];i;i=e[i].next){
        int v=e[i].v;
        if(v==fa[p])continue;
        fa[v]=p;
        dfs(v);
        for(int j=1;j<=k;++j)siz[p][j]+=siz[v][j-1];
    }
}
inline int solve(int p){
    int ret=siz[p][k],pos=k-1;
    while(fa[p]&&pos!=-1){
        ret+=siz[fa[p]][pos]-(pos?siz[p][pos-1]:0);
        --pos,p=fa[p];
    }
    return ret;
}
int main(){
    n=read(),k=read();
    for(int i=1;iint u=read(),v=read();
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;++i)siz[i][0]=read();
    dfs(1);
    for(int i=1;i<=n;++i)for(int j=1;j<=k;++j)siz[i][j]+=siz[i][j-1];
    for(int i=1;i<=n;++i)write(solve(i)),puts("");
    return 0;
}
wp7 화면 캡처 코드
[코뮤니티 모각코] 웹 리액트 과정 - 3주차

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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