CodeForces-960E Alternating Tree

传送门：CodeForces-960E

思路分析

考虑进行树DP，显然偶数路径的总权值是0，因为来回抵消了，所以统计答案的时候只需要计算奇数路径
$siz[u][0/1]$记录u的子树中，以u结尾的偶/奇路径个数
$dis[u][0/1]$记录u的子树中，以u结尾的偶/奇路径权值和

最后答案*2，因为双向都要算一遍，再加上单个点的贡献

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N = 2e5+10;
const int mod= 1e9+7;

#define int long long

vector<int>e[N];
int dis[N][2],siz[N][2],n,ans,w[N];

void dfs(int u,int fa){
    siz[u][1]=1;
    dis[u][1]=(w[u]+mod)%mod;
    for(auto v:e[u]){
        if(v==fa) continue;
        dfs(v,u);
        ans=(ans+dis[u][0]*siz[v][1]%mod+dis[v][1]*siz[u][0]%mod)%mod;
        ans=(ans+dis[u][1]*siz[v][0]%mod+dis[v][0]*siz[u][1]%mod)%mod;
        siz[u][0]+=siz[v][1];
        siz[u][1]+=siz[v][0];
        dis[u][0]=(dis[u][0]+dis[v][1]-w[u]*siz[v][1]%mod+mod)%mod;
        dis[u][1]=(dis[u][1]+dis[v][0]+w[u]*siz[v][0]%mod+mod)%mod;
    }
}


signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    read(n);
    for(int i=1;i<=n;i++) read(w[i]);
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        e[u].pb(v);
        e[v].pb(u);
    }
    dfs(1,1);
    ans*=2;
    ans%=mod;
    for(int i=1;i<=n;i++) ans=(ans+w[i]+mod)%mod;
    cout<<ans<<endl;




    return 0;
}

?