hdu4916 Count on the path, 트리 dp

1975 단어 dpHDU
물 문제를 한참 동안 풀어도 취했다.
1번 노드를 루트로 하고 경로가 루트를 통과하지 않으면 1.만약 뿌리를 통과한다면 두 개의 트리로 나누어 이 두 개의 트리 중 경로에 없는 최소값과 다른 트리의 최소값을 찾아라.
대략적인 과정은 dfs () 이며, 각 점 아래의 최소값을 찾습니다.ffs3 (), 모든 점이 위에서 아래로 경로에 없는 최소값을 찾습니다.
ffs2 () 점마다 있는 하위 나무를 찾습니다.
못생긴 코드인데 내일 시합이 있어서 고치기 귀찮아!
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
using namespace std;
#define NN 1001000
#define inf 1000000100

struct edge{int v,ne;}ed[NN*2];
int te,fi[NN];

int n;

int branch[NN],smin[10],sb[10],f[NN];
int ch[NN][2],son[NN];

void init_edge(){
    te=-1;
    memset(fi,-1,sizeof(fi));
}

void addedge(int fr,int to){
    te++;ed[te].ne=fi[fr];fi[fr]=te;ed[te].v=to;
}

void dfs(int u,int fa){
    int e,v,tmp;
    f[u]=inf;
    ch[u][0]=ch[u][1]=inf;
    son[u]=-1;
    for(e=fi[u];e!=-1;e=ed[e].ne){
        v=ed[e].v;
        if (v==fa) continue;
        dfs(v,u);
        tmp=min(v,f[v]);
        if (tmpb) swap(a,b);
    if (a==1&&b==1) return 2;
    else if (a==1){
        for(i=1;i<=3;++i){
            if (branch[b]!=sb[i]) break;
        }
        return min(smin[i],f[b]);
    }
    else {
        if (branch[a]==branch[b]) return 1;
        for(i=1;i<=3;++i){
            if (!(branch[a]==sb[i]||branch[b]==sb[i])) break;
        }
        return min(f[a],min(smin[i],f[b]));
    }
}

int main(){
    int q;
    int i,a,b,e,v,ans,la,tmp;
    while(scanf("%d%d",&n,&q)!=EOF){
        init_edge();
        for(i=1;i

좋은 웹페이지 즐겨찾기