Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"OOOVOOO","updateTime":1562825390000,"title":"天天爱跑步(挂)","dislikeCnt":0,"content":"```\n#include\u003ciostream\u003e\n#include\u003ccstdio\u003e\n#include\u003ccstring\u003e\nusing namespace std;\nconst int maxn\u003d300005;\nint f[maxn][20],d[maxn];\nint m,n;\nint a[maxn];\nint v[maxn];\nint ans[maxn];\nstruct tree{\n\tint e,nt;\n}t[maxn*2];\nint nt[maxn],tot;\ninline void add(int s,int e)\n{\n\tt[++tot].e\u003de;\n\tt[tot].nt\u003dnt[s];\n\tnt[s]\u003dtot;\n}\nvoid dfs(int k)\n{\n\tfor(int q\u003d1;q\u003c20;q++)\n\t{\n\t\tif(!f[f[k][q-1]][q-1])\n\t\t\tbreak;\n\t\tf[k][q]\u003df[f[k][q-1]][q-1];\n\t}\n\tfor(int q\u003dnt[k];q;q\u003dt[q].nt)\n\t\tif(!v[t[q].e])\n\t\t{\n\t\t\tv[t[q].e]\u003d1;\n\t\t\tf[t[q].e][0]\u003dk;\n\t\t\td[t[q].e]\u003dd[k]+1;\n\t\t\tdfs(t[q].e);\n\t\t}\n}\ninline int lca(int x,int y)\n{\n\tif(d[x]\u003ed[y])\n\t\tswap(x,y);\n\twhile(d[x]!\u003dd[y])\n\t\tfor(int q\u003d0;;q++)\n\t\t\tif(d[f[y][q]]\u003cd[x])\n\t\t\t{\n\t\t\t\ty\u003df[y][q-1];\n\t\t\t\tbreak;\n\t\t\t}\n\tif(x\u003d\u003dy)\n\t\treturn x;\n\twhile(f[x][0]!\u003df[y][0])\n\t\tfor(int q\u003d0;;q++)\n\t\t\tif(f[x][q]\u003d\u003df[y][q])\n\t\t\t{\n\t\t\t\tx\u003df[x][q-1],y\u003df[y][q-1];\n\t\t\t\tbreak;\n\t\t\t}\n\treturn f[x][0];\n}\nint main()\n{\n\tcin\u003e\u003en\u003e\u003em;\n\tfor(int q\u003d1;q\u003cn;q++)\n\t{\n\t\tint x,y;\n\t\tcin\u003e\u003ex\u003e\u003ey;\n\t\tadd(x,y),add(y,x);\n\t}\n\tv[1]\u003dd[1]\u003d1;\n\tdfs(1);\n\tfor(int q\u003d1;q\u003c\u003dn;q++)\n\t{\n\t\tcout\u003c\u003cq\u003c\u003c\":\";\n\t\tfor(int w\u003d0;w\u003c20;w++)\n\t\t\tcout\u003c\u003cf[q][w]\u003c\u003c\" \";\n\t\tcout\u003c\u003cendl;\n\t}\n\tint x,y;\n\tfor(int q\u003d1;q\u003c\u003dn;q++)\n\t\tcin\u003e\u003ea[q];\n\tfor(int q\u003d1;q\u003c\u003dm;q++)\n\t{\n\t\tcin\u003e\u003ex\u003e\u003ey;\n\t\tint ff\u003dlca(x,y);\n\t\tcout\u003c\u003cff\u003c\u003cendl;\n\t\tint nans\u003dd[x]+d[y]-d[ff];\n\t\tif(a[y]\u003d\u003dnans)\n\t\t\t++ans[y];\n\t}\n\tfor(int q\u003d1;q\u003c\u003dn;q++)\n\t\tcout\u003c\u003cans[q]\u003c\u003c\" \";\n\tcout\u003c\u003cendl;\n}\n```","likeCnt":0,"createTime":1562825390000,"isWorkbook":false,"viewCnt":825,"openness":1,"fav":false,"id":1278,"trustable":false}