\u4f5c\u4e3a\u4e00\u9053NOI\u7684\u9898\uff0c\u5b83\u4e00\u5ea6\u4ee4\u6211\u4ee5\u4e3a\u5b83\u662f2001\u7684\u3002
\n\u4e0d\u66fe\u60f3\uff0cNOI\u7adf\u7136\u6709\u8fd9\u4e48\u6c34\u7684\u9898\u3002
\n\u6211\u4e00\u5f00\u59cb\u4ee5\u4e3a\u81ea\u5df1\u7684\u5199\u6cd5\u9519\u4e86\u3002
\n\u4f46\u662f…
\n\u5509\uff0c\u53cd\u6b63\u5c31\u662f\u8ba1\u7b97\u5b50\u6811\u5927\u5c0f\u5c31\u5bf9\u4e86\u3002
\n\u53e6\uff1a\u5b58\u6811\u7684\u65f6\u5019\u7edd\u00b7\u5bf9\u00b7\u4e0d\u00b7\u53ef\u00b7\u4ee5\u300cu>v?u^=v^=u^=v:0\u300d\uff01\uff01\uff01\u8fd9\u6837\u4f1a\u5bfc\u81f4\u9519\u8bef\u3002\u53cd\u4f8b\uff1a1->3,3->2\u3002NOIP\u56e0\u4e3a\u8fd9\u4e2a\u4e22\u4e86\u5f88\u591a\u5206\u3002<\/p>\n
#include<iostream>\r\n#include<cstdio>\r\n#include<cmath>\r\n\r\nstruct ee{\r\n int v;\r\n int w;\r\n int nxt;\r\n}e[2000005];\r\nint h[1000005],et=0;\r\ninline void add(int u,int v,int w){\r\n e[++et]=(ee){v,w,h[u]};\r\n h[u]=et;\r\n}\r\n\r\nint n,in[1000005];\r\nint f[10000005];\r\nbool vis[1000005];\r\nlong long ans=0;\r\ninline void dfs(int X){\r\n for(int i=h[X];i;i=e[i].nxt){\r\n if(vis[e[i].v]==1){\r\n continue;\r\n }\r\n vis[e[i].v]=1;\r\n dfs(e[i].v);\r\n ans+=1LL*e[i].w*(std::abs(((f[e[i].v]<<1)-n)));\r\n f[X]+=f[e[i].v];\r\n }\r\n ++f[X];\r\n}\r\n\r\n\r\nvoid init(){\r\n scanf(\"%d\",&n);\r\n int u,v,w;\r\n for(int i=1;i<n;++i){\r\n scanf(\"%d%d%d\",&u,&v,&w);\r\n add(u,v,w);\r\n add(v,u,w);\r\n }\r\n vis[1]=1;\r\n dfs(1);\r\n printf(\"%lld\",ans);\r\n}\r\n\r\nint main(){\r\n init();\r\n return 0;\r\n}<\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u4f5c\u4e3a\u4e00\u9053NOI\u7684\u9898\uff0c\u5b83\u4e00\u5ea6\u4ee4\u6211\u4ee5\u4e3a\u5b83\u662f2001\u7684\u3002 \u4e0d\u66fe\u60f3\uff0cNOI\u7adf\u7136\u6709\u8fd9\u4e48\u6c34\u7684\u9898\u3002 \u6211\u4e00\u5f00\u59cb\u4ee5\u4e3a\u81ea\u5df1\u7684\u5199\u6cd5\u9519 … <\/p>\n