2084. asm.def的基本算法
傳送門
★☆ 輸入檔案：<code>asm_algo.in</code> 輸出檔案：<code>asm_algo.out</code> 簡單對比
時間限制：1 s 記憶體限制：256 mb
“有句美國俗語說，如果走起來像鴨子，叫起來像鴨子，那就是一隻鴨子。”斯科特·華萊士看着asm.def面前螢幕上滾動的綠色字元，若有所思地說。
“什麼意思？”
“你的資料。看上去是一棵樹。”
“按照保密條令，我什麼也不說這是最好的——但見你這麼熱情，一句話不說也不好。”asm.def停下手中的快速數論變換，“确實是樹。”
“然後你怎麼算出來目标的位置？”
“都需要按照基本算法，按照圖論的那一套理論，去産生。聽說過lca嗎？不是那個印度飛機，我是說最近公共祖先……”
asm.def通過分析無線電信号得到了一棵有n個節點，以1為根的樹。除1之外，節點i的父親是p_i。節點帶有權值，節點i的權值是w_i。
我們定義某點的祖先為從根到它路徑上的所有點（包括它本身），而兩個節點a、b的最近公共祖先是某個點p，使得p同時是a、b的祖先，而且p離根最遠。
asm.def想要求出
（文字：∑∑w_i*w_j*w_lca(i,j)），
其中lca(i,j)是i、j的最近公共祖先，他認為這個值至關重要。由于這個值可能很大，asm.def隻需要知道它模1,000,000,007（即10^9+7）的結果。
第1行兩個整數：n和w_1.
第2行到第n行，第i行有兩個整數p_i和w_i。
一行一個整數，即答案模1,000,000,007的值。
1×1×1+1×2×2+2×1×2+2×2×2=17。
對于30%的資料，n<=100，w_i<=10。
對于60%的資料，n<=1000，w_i<=1000.
對于100%的資料，1<=n<=10^5，0<=w_i<=10^9，1<=p_i<i.
【逾時code】
dalao說沒事先打暴力，說不定會想出思路，然而并沒有。逾時4個點。
用define定義的mod一直錯 輸出1e009...
然後建邊時沒有建雙邊....
樹剖寫錯.....
【ac code】
一氣之下全改成long long 就過了。
【思路】
如圖的矩陣表示i,j的lca。發現對角線兩側是對稱的（因為i,j的lca==j,i的lca）；
那麼我們隻要求出對角線的一側的值再*2+對角線上的值就是答案。