{"id":833,"date":"2019-03-27T21:57:36","date_gmt":"2019-03-27T13:57:36","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=833"},"modified":"2019-03-27T21:58:13","modified_gmt":"2019-03-27T13:58:13","slug":"lp2634-%e5%9b%bd%e5%ae%b6%e9%9b%86%e8%ae%ad%e9%98%9f-%e8%81%aa%e8%81%aa%e5%8f%af%e5%8f%af","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/03\/27\/lp2634-%e5%9b%bd%e5%ae%b6%e9%9b%86%e8%ae%ad%e9%98%9f-%e8%81%aa%e8%81%aa%e5%8f%af%e5%8f%af\/","title":{"rendered":"lp2634 \u56fd\u5bb6\u96c6\u8bad\u961f \u806a\u806a\u53ef\u53ef"},"content":{"rendered":"\n<p>\u8fd9\u4e00\u9898\u672c\u8d28\u4e0a\u548c\u90a3\u9053\u300c\u6a21\u677f \u70b9\u5206\u6cbb1\u300d\u662f\u4e00\u6837\u7684\uff0c\u76f4\u63a5\u4e00\u8fb9\u7edf\u8ba1\u4e00\u8fb9\u53d6\u6a21\u5373\u53ef\u3002 <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;iostream>\n#include&lt;cstdio>\n#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) \n\ntypedef long long ll;\n\ninline int Max(int A,int B){\n\treturn A>B?A:B;\n}\ninline ll gcd(ll A,ll B){\n\treturn B?gcd(B,A%B):A;\n}\n\nstruct ee{\n\tint v;\n\tint w;\n\tint nxt;\n}e[40005];\nint h[20005],et=0;\ninline void Eadd(int U,int V,int W){\n\te[++et]=(ee){V,W,h[U]};\n\th[U]=et; \n}\ninline void add(int U,int V,int W){\n\tEadd(U,V,W);\n\tEadd(V,U,W);\n}\n\nint n,rt=0,s;\nint vis[20005],sz[20005],mx[20005];\ninline void dfs0(int X,int FA){\n\tsz[X]=1,mx[X]=0;\n\tFv(i,X){\n\t\tif(e[i].v==FA||vis[e[i].v]){\n\t\t\tcontinue;\n\t\t}\n\t\tdfs0(e[i].v,X);\n\t\tsz[X]+=sz[e[i].v];\n\t\tmx[X]=Max(mx[X],sz[e[i].v]);\n\t}\n\tmx[X]=Max(mx[X],s-sz[X]);\n\tif(mx[X]&lt;mx[rt]){\n\t\trt=X;\n\t}\n}\nint exist[3],dis[20005],st[20005],st2[20005],tp=0,tp2=0;\nll ans=0;\ninline void dfs2(int X,int FA){\n\tst[++tp]=dis[X];\n\tFv(i,X){\n\t\tif(e[i].v==FA||vis[e[i].v]){\n\t\t\tcontinue;\n\t\t}\n\t\tdis[e[i].v]=dis[X]+e[i].w;\n\t\tdfs2(e[i].v,X);\n\t}\n}\ninline void calc(int X){\n\ttp2=0;\n\tFv(i,X){\n\t\tif(vis[e[i].v]){\n\t\t\tcontinue;\n\t\t}\n\t\ttp=0;\n\t\tdis[e[i].v]=e[i].w;\n\t\tdfs2(e[i].v,X);\n\t\tfor(int j=1;j&lt;=tp;++j){\n\t\t\tans+=exist[(3-st[j]%3)%3];\n\t\t}\n\t\tfor(int j=1;j&lt;=tp;++j){\n\t\t\tst2[++tp2]=st[j];\n\t\t\t++exist[st[j]%3];\n\t\t}\n\t}\n\tfor(int i=0;i&lt;3;++i){\n\t\texist[i]=0;\n\t}\n}\n\ninline void dfs1(int X){\n\texist[0]=vis[X]=1;\n\tcalc(X);\n\tFv(i,X){\n\t\tif(vis[e[i].v]){\n\t\t\tcontinue;\n\t\t}\n\t\trt=0;\n\t\ts=sz[X];\n\t\tdfs0(e[i].v,X);\n\t\tdfs1(rt);\n\t}\n}\n\nvoid init(){\n\tscanf(\"%d\",&amp;n);\n\tint u,v,w;\n\tfor(int i=1;i&lt;n;++i){\n\t\tscanf(\"%d%d%d\",&amp;u,&amp;v,&amp;w);\n\t\tadd(u,v,w);\n\t} \n\trt=0,mx[0]=n;\n\tdfs0(1,0);\n\tdfs1(1);\n\tans=(ans&lt;&lt;1)+n;\n\tll g=gcd(ans,n*n);\n\tprintf(\"%lld\/%lld\\n\",ans\/g,(n*n)\/g);\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u8fd9\u4e00\u9898\u672c\u8d28\u4e0a\u548c\u90a3\u9053\u300c\u6a21\u677f \u70b9\u5206\u6cbb1\u300d\u662f\u4e00\u6837\u7684\uff0c\u76f4\u63a5\u4e00\u8fb9\u7edf\u8ba1\u4e00\u8fb9\u53d6\u6a21\u5373\u53ef\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[17,30,56,8,105,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/833"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=833"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/833\/revisions"}],"predecessor-version":[{"id":835,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/833\/revisions\/835"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=833"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=833"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=833"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}