TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

57.1% (4/7)

Description

給你一棵有 $n$ 個節點的樹,節點編號由 $1$ 到 $n$,第 $i$ 個節點有一個權值 $V_i$。

一個從 $u_1$ 到 $u_m$ 的簡單路徑是 $u_1$ 到 $u_m$ 在樹上的最短路徑,由 $m$ 個節點組成,也就是 $u_1\rightarrow u_2\rightarrow u_3\rightarrow \cdots \rightarrow u_{m−1}\rightarrow u_m$。一個路徑對應到整數的函數 $A(u_1,u_m)$ 被定義為 $\displaystyle A(u_1,u_m)=\sum_{i=1}^ {m}(−1)^ {i+1}\cdot V_{u_i}$。一個路徑可以包含 $0$ 條邊,也就是 $u_1=u_m$ 。

請計算樹上所有不重複的簡單路徑的 $A$ 函數的和。請注意這邊的路徑是有向的:兩條路徑相異若且唯若起點相異或終點相異。
因為答案可能很大,請輸出它除以 $10^ 9+7$ 的餘數。

請給出 edit distance 與下列程式碼不超過 $20$ 的解。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e9 + 7;
ll norm(ll &s)
{
    return ((s%M)+M)%M;
}
struct dp
{
    ll v,s,w[2],c[2];
    dp(ll k) : v(k), s(k), w{0,k}, c{0,1} {}
    dp operator += (const dp & r) 
    {
        s = norm(s + r.s + w[0] * r.c[1] + w[1] * r.c[0] + r.w[0] * c[1] + r.w[1] * c[0]);
        w[0] = norm(w[0] + r.w[1] - v * r.c[1]);
        w[1] = norm(w[1] + r.w[0] + v * r.c[0]);
        c[0] = norm(c[0] + r.c[1]);
        c[1] = norm(c[1] + r.c[0]);
        return *this;
    }
};
const int N = 2e5 + 98;
ll v[N];
vector<int> g[N];
dp dfs(int p,int u)
{
    dp now(v[u]);
    for (int w : g[u])
        if (w != p) 
            now += dfs(u,w);
    return now;
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
        v[i] = norm(v[i]);
        g[i].clear();
    }
    for (int i = 0; i < n-1; ++i) {
        int u,v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    cout << norm(dfs(0,1).s * 2) << endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
}

Input Format

輸入的第一行有一個正整數 $T\ (1 \le T \le 10)$,代表測試資料的筆數。

每筆測試資料第一行包含一個正整數 $n\ (2\le n \le 2\cdot 10^ 5)$ 代表樹的節點的數量。

第二行包含 $n$ 個用空白隔開的整數 $V_1,V_2,\cdots,V_n\ (−10^ 9
\le V_i \le 10^ 9)$ 代表節點的權值。

接下來 $n−1$ 行,每行包含兩個用空白隔開的正整數 $u$ 跟 $v\ (1\le
u,v\le n,\ u \neq v)$ ,代表連接 $u$ 跟 $v$ 節點的邊。
保證輸入所建出的圖是一棵樹。

Output Format

對於每筆測試資料,請輸出樹上所有不重複的簡單路徑的樹變數函數的和除以 $10^ 9+7$ 的餘數。

Sample Input

2
4
-4 1 5 -2
1 2
1 3
1 4
8
-2 6 -4 -4 -9 -3 -7 23
8 2
2 3
1 4
6 5
7 6
4 7
5 8

Sample Output

40
4

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144