//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 的格式要求是 "插入 [该代码片段的中文名]"

{
    "树形dp": {
        "prefix": "acm-4.5没有上司的舞会",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#define R register int",
            "using namespace std;",
            "int head[6010],a,b,t,i,j,n,f[6010][2],pan[6010];",
            "struct QAQ{int next,to;}Q[6010];",
            "inline void add(int x,int y){Q[++t].to=y,Q[t].next=head[x],head[x]=t;}",
            "inline void dfs(int w){",
            "    for(R k=head[w];k;k=Q[k].next){",
            "        int to=Q[k].to;",
            "        dfs(to);",
            "        f[w][0]+=max(f[to][0],f[to][1]);",
            "        f[w][1]+=f[to][0];",
            "    }",
            "}",
            "int main(){",
            "    scanf(\"%d\",&n);",
            "    for(i=1;i<=n;i++)scanf(\"%d\",&f[i][1]);",
            "    for(i=1;i<n;i++)scanf(\"%d%d\",&a,&b),pan[a]++,add(b,a);",
            "    for(i=1;i<=n;i++)",
            "        if(!pan[i]){",
            "            dfs(i);",
            "            printf(\"%d\\n\",max(f[i][0],f[i][1]));",
            "            return 0;",
            "        }",
            "}",
            ""
        ],
        "description": "插入 树形dp"
    }
}