//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "保安站岗，皇宫看守": {
        "prefix": "acm-4.5树形dp",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#define R register int",
            "using namespace std;",
            "struct QAQ{int to,next;}a[1505]; ",
            "int m,pan[1505],n,t,w[1505],dp[1505][3],head[1505];",
            "inline void add(int x,int y){a[++t].to=y,a[t].next=head[x],head[x]=t;}",
            "  //dp[i][0] 以及各种情况的具体转移方程和初始状态 ",
            "inline void dfs(int x){",
            "    R i,to,dd=0xfffffff;",
            "    dp[x][1]=w[x];dp[x][2]=0;dp[x][0]=0;",
            "    for(i=head[x];i;i=a[i].next){",
            "        dfs(to=a[i].to);",
            "        dd=min(dd,dp[to][1]-min(dp[to][0],dp[to][1]));",
            "        dp[x][0]+=min(dp[to][0],dp[to][1]);",
            "        dp[x][1]+=min(dp[to][1],dp[to][2]);",
            "        dp[x][2]+=min(dp[to][0],dp[to][1]);",
            "    }",
            "    dp[x][0]+=dd;",
            "}",
            "int main(){",
            "\tmemset(dp,127,sizeof(dp));",
            "    scanf(\"%d\",&n);",
            "    R i,j,a,k,r;",
            "    for(i=1;i<=n;i++){",
            "        scanf(\"%d%d%d\",&a,&k,&m);w[a]=k;",
            "        for(j=1;j<=m;j++)scanf(\"%d\",&r),pan[r]=1,add(a,r);",
            "    }",
            "    for(i=1;i<=n;i++)",
            "        if(!pan[i]){",
            "            dfs(i);",
            "            printf(\"%d\",min(dp[i][1],dp[i][0]));",
            "            return 0;",
            "        }",
            "}",
            ""
        ],
        "description": "插入 保安站岗，皇宫看守"
    }
}