题意

给出一个 n 个点、m 条边的有向无环图。求 \(\sum_{i=1}^{n}\sum_{j=1}^{n}count(i,j)\cdot a_i\cdot b_j\)，\(count(i, j)\) 表示从 i 到 j 不同的路径数量。

分析

树形DP。

dp[i] 表示从 i 点出发可以到达的所有子孙的 b 的和。

code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;const int MAXN = 1e5 + 10;const ll MOD = 1e9 + 7;int n, m;ll a[MAXN], b[MAXN];vector
         
           G[MAXN];ll ans;ll dp[MAXN];void dfs(int u) { if(dp[u] != -1) return; dp[u] = 0; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; dfs(v); dp[u] = (dp[u] + dp[v] + b[v]) % MOD; }}int main() { while(~scanf("%d%d", &n, &m)) { for(int i = 1; i <= n; i++) { G[i].clear(); scanf("%lld%lld", &a[i], &b[i]); } memset(dp, -1, sizeof dp); for(int i = 0; i < m; i++) { int x, y; scanf("%d%d", &x, &y); G[x].push_back(y); } ans = 0; for(int i = 1; i <= n; i++) { dfs(i); ans = (ans + a[i] * dp[i]) % MOD; } printf("%lld\n", ans); } return 0;}