NOIp2014提高組

【題目描述】

無向連通圖G 有n 個點，n - 1 條邊。點從1 到n 依次編號，編號為 i 的點的權(quán)值為W i?? ，每條邊的長度均為1 。圖上兩點( u ,??v ) 的距離定義為u 點到v 點的最短距離。對于圖G 上的點對( u, v) ，若它們的距離為2 ，則它們之間會產(chǎn)生Wu
×Wv 的聯(lián)合權(quán)值。?
請問圖G 上所有可產(chǎn)生聯(lián)合權(quán)值的有序點對中，聯(lián)合權(quán)值最大的是多少？所有聯(lián)合權(quán)值之和是多少？

【輸入輸出格式】

輸入格式：

輸入文件名為link .in。?
第一行包含1 個整數(shù)n 。?
接下來n - 1 行，每行包含 2 個用空格隔開的正整數(shù)u 、v ，表示編號為 u 和編號為v 的點之間有邊相連。?
最后1 行，包含 n 個正整數(shù)，每兩個正整數(shù)之間用一個空格隔開，其中第 i 個整數(shù)表示圖G 上編號為i 的點的權(quán)值為W i 。

輸出格式：

輸出文件名為link .out 。?
輸出共1 行，包含2 個整數(shù)，之間用一個空格隔開，依次為圖G 上聯(lián)合權(quán)值的最大值
和所有聯(lián)合權(quán)值之和。由于所有聯(lián)合權(quán)值之和可能很大，輸出它時要對10007 取余。

【輸入輸出樣例】

輸入樣例#1：

5 1 2 2 3 3 4 4 5 1 5 2 3 10

輸出樣例#1：

20 74

【說明】

???? 本例輸入的圖如上所示，距離為2 的有序點對有( 1,3) 、( 2,4) 、( 3,1) 、( 3,5) 、( 4,2) 、( 5,3) 。?
其聯(lián)合權(quán)值分別為2 、15、2 、20、15、20。其中最大的是20，總和為74。?

【數(shù)據(jù)說明】

?對于30% 的數(shù)據(jù)，1 < n≤ 100 ；?
對于60% 的數(shù)據(jù)，1 < n≤ 2000；?
對于100%的數(shù)據(jù)，1 < n≤ 200 , 000 ，0 < wi≤ 10, 000 。

【思路】

　60%：用暴力搜索可以將解決60%的數(shù)據(jù)，如果i和j相連，j和k相連，i和k不相連，那么可以認為i和k可以構(gòu)成聯(lián)合最大權(quán)值，用一個O（N^3）的循環(huán)即可。

　100%：

　　這個題AC的思路很多，可以跑樹，用LCA處理兩個兄弟之間的關(guān)系，也可以跑圖，想要，存儲一定要用前向星。（不會問度娘）。我能夠AC還要感謝@yangs_s，如果不是他的博客http://blog.csdn.net/yangs_s/article/details/47359967，這個題我也做不出AC來的，我在這里把他的思路說一下吧。

　　有兩個關(guān)鍵點。

　　首先輸出分為兩部分，可以把題目分成兩部分來看，對一個點來說，最大的乘積自然就是和它相鄰的兩個權(quán)值最大的節(jié)點的權(quán)值的乘積， 讀入后順手處理一下就能出來。

　　第二個關(guān)鍵點就是加法結(jié)合律。

　　沒錯，加法結(jié)合律！

　　我看到神犇的博客后伏案長嘆，這是小學(xué)三年級的內(nèi)容，我就這樣還給老師了。

　　我們假設(shè)和o點相鄰的點有a,b,c,d,e,f,g七個，假設(shè)他們的權(quán)值就是a,b,c,d,e,f,g。某二逼青年的計算過程是這樣的：sum：=a·b+a·c+a·d…….+a….+e*g….,但其實我們這樣處理，我們先用加法運算法則，發(fā)現(xiàn)sum其實就是每個點的權(quán)值乘以可以聯(lián)合（距離為2）的節(jié)點的所有權(quán)值之和，所以說，我們在讀入數(shù)據(jù)的時候，可以預(yù)先處理一下，把每個節(jié)點周圍相鄰節(jié)點的權(quán)值之和給加起來，就以上述為例，在處理時，把a,b,c….g的權(quán)值加起來為s[o]{o點相鄰點的權(quán)值之和}，然后在計算時，就可以用sum:=a·(s[o]-a)+b·(s[o]-b)…..很自然的結(jié)果就出來了!

　　算法的時間復(fù)雜度應(yīng)該是O（kn），k應(yīng)該是一個很小很小遠小于N的常數(shù)，應(yīng)該和LCA的差不多了吧。?

const ma=10007; const mx=200000;type ss=recordu,v:longint;end;var s:array[1..mx] of int64;//s[i]表示和結(jié)點i所有相連的點的權(quán)值之和e:array[1..mx] of ss;//存的是邊w,max1,max2:array[1..mx]of longint; {w[i]表示第i個點的權(quán)值max1[i]表示和i相連得結(jié)點中權(quán)值最大的結(jié)點max2[i]表示和i相連得結(jié)點中權(quán)值最小的結(jié)點}n,i,j,ans1,ans2:longint;procedure box; var i,j:longint; beginfillchar(s,sizeof(s),0);fillchar(e,sizeof(e),0);fillchar(w,sizeof(w),0);fillchar(max1,sizeof(max1),0);fillchar(max2,sizeof(max2),0);ans1:=0;ans2:=0; end; //變量初始化procedure work(x:longint;var a,b:longint); //x的值是不會被改變的，a和b是可以被改變的 begin //首先已經(jīng)得出值的數(shù)組是合法的，再次更改過后也一定是合法的if x>a thenbeginb:=a;a:=x;endelseif x>b then b:=x; end; //用來比較大小的過程，必須用全局變量procedure change; var i,u,v:longint; beginfor i:=1 to n-1 dobeginu:=e[i].u;v:=e[i].v;inc(s[u],w[v]);inc(s[v],w[u]);work(w[v],max1[u],max2[u]);work(w[u],max1[v],max2[v]);//不斷更新結(jié)點周圍的最大值和次大值end; end; //預(yù)處理程序procedure main1; var i:longint; beginfor i:=1 to n doif max1[i]*max2[i]>ans1 thenans1:=max1[i]*max2[i]; end; //處理最大的聯(lián)合權(quán)值procedure main2; var i,j,u,v:longint; beginfor i:=1 to n-1 dobeginu:=e[i].u;v:=e[i].v;ans2:=(ans2+((s[u]-w[v])*w[v]) mod ma) mod ma;ans2:=(ans2+((s[v]-w[u])*w[u]) mod ma) mod ma;end; end; //處理權(quán)值之和procedure init; var i,j:longint; beginreadln(n);for i:=1 to n-1 doreadln(e[i].u,e[i].v);for i:=1 to n do read(w[i]); end;procedure printf; beginwriteln(ans1,' ',ans2); end;beginbox;init;change;main1;main2;printf; end.

?

轉(zhuǎn)載于:https://www.cnblogs.com/yangqingli/p/4721774.html

總結(jié)

以上是生活随笔為你收集整理的[NOIP2014]联合权值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。