编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 53ms

├ 测试数据 10：答案正确... 38ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：91ms

好慢啊.......悲哀

大牛指点下为什么全部 程序输出比正确答案长

type pt=^node;

node=record

n,d:longint;

next:pt;

end;

var sum,min:int64;mini:longint;

i,j,k,t,n:longint;

m:array[1..100000] of pt;

d,s1,s,total:array[0..100000] of int64;

procedure init(a,b,c:longint);

var p:pt;

begin

p:=m[a];

while p^.nextnil do p:=p^.next;

new(p^.next);

p^.next^.n:=b;

p^.next^.d:=c;

p^.next^.next:=nil;

end;

procedure search1(i,last:longint;dis:int64);

var p:pt;

begin

d[i]:=dis;

p:=m[i];

total[1]:=total[1]+s[i]*dis;

while p^.nextnil do

begin

p:=p^.next;

if p^.nlast then search1(p^.n,i,p^.d+dis);

end;

end;

function search2(i,last:longint):int64;

var p:pt;

begin

search2:=0;

p:=m[i];

while p^.nextnil do

begin

p:=p^.next;

if p^.nlast then

begin

if p^.nextnil then s[p^.n]:=s[p^.n]+search2(p^.n,i);

search2:=search2+s[p^.n];

end;

end;

end;

begin

readln(n);

for i:=1 to n do

begin

new(m[i]);

m[i]^.next:=nil;

end;

for i:=1 to n do

begin

read(s[i]);

sum:=sum+s[i];

end;

for t:=1 to (n-1) do

begin

readln(i,j,k);

init(i,j,k);

init(j,i,k);

end;

search1(1,1,0);

s[1]:=search2(1,1);

for i:=2 to n do

total[i]:=total[1]+(sum-s[i]*2)*d[i];

min:=100000000;

for i:=1 to n do

if total[i]

要 int64 !!! 被阴了一次

既然要 int64 , 无穷大就不是 maxlongint 了，又被阴了一次。。。

非常基本的 TreeDP，大体的思路就是两次 DFS，下面是核心代码

procedure DP_1 (u , fa : longint) ;

var p : longint ;

begin

p := vr ; size := stu ;

while (p -1) do begin

if (arc[p].d fa) then begin

DP_1 (arc[p].d , u) ;

inc (size , size[arc[p].d]) ;

inc (sum , sum[arc[p].d] + arc[p].w * size[arc[p].d]) ;

end ;

p := arc[p].next ;

end ;

end ;

procedure DP_2 (u , fa : longint) ;

var p : longint ;

begin

if (f < ans) then begin

loc := u ;

ans := f ;

end ;

p := vr ;

while (p -1) do begin

if (arc[p].d fa) then begin

f[arc[p].d] := f + arc[p].w * (size[1] - size[arc[p].d] * 2) ;

DP_2 (arc[p].d , u) ;

end ;

p := arc[p].next ;

end ;

end ;

很显然我的代码一部分被吃了。。。。

直接用链表上，不用排序。

遵照大牛指示，除了循环变量全改成了int64。

一次AC了。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 134ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：190ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 353ms

├ 测试数据 10：答案正确... 338ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：691ms

O(n)的怎么这么慢啊，就排序nlog(n)，靠。。。。。。

莫名其妙WA了无数回....

然后莫名其妙的AC...

做两次TreeDP，具体地就不说了。

注意数据类型要开int64（我看了题解才知道……）

还有没有bt数据，递归不会爆栈。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：66ms

编译通过...

├ 测试数据 01：答案错误...程序输出比正确答案长

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 119ms

├ 测试数据 10：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：238ms

为何第一点会错...

交了三次····第一次longint···3个点

第2次将DP的数组开到int64。。。6个点

妈的，第三次把所有能开成int64的全开成int64。。。过了

树形DP

上去一遍下来一遍完事。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：207ms

第一次算法打错,第二次没用INT64,第三次。。。才。。。

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 56ms

傻傻的刚开始n看成了1000,没用链表存,改下就过了

int64!!!

预处理就错了

怪不得WA

program Dzs;

type

qq=record

x,y,z:longint;

end;

var

a:extended;

b,c,d,i,j,m,n,s:longint;

qw:qq;q:array[0..200000]of qq;

w1,f1,l:array[0..100000]of longint;

q1,q3:array[0..100000]of extended;

procedure sort(a,b:longint);

var i,j,k:longint;

begin

i:=a;j:=b;

k:=q[(a+b)div 2].x;

while i

我太垃圾了，连建树都不会……

大家给个思路啊..我认为此题该用图做。.大家说下方法啊

d[i] i到父亲的距离

s[i] i以及子树的节点权和

tot[i] 集中到i的花费

sum 所有节点权和

设i为x的子节点

tot[i] = tot[x]+(sum-2*s[i])*d[i];

两次dps处理

竟然一遍AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：50ms

树形DP，O(n log n).

因为int64的速度太慢，没有秒杀。

我的贡献：提高本题通过率1个百分点。

　各位大牛能讲一下方法不；

　

　非常感谢