题解：P10842 【MX-J2-T3】Piggy and Trees

· · 题解

三倍DFS 三倍快乐(计算点权值)

一眼看上去好像不难？

首先想到的就是DFS计算每个点的权值:\ 对于每一个点，讨论这个点作为 \Large{x} (见题目) 的情况。\ \ 若把中间点 \Large{x} 作为根节点，对于非零的 f(u, v, i) 一定有:

于是我们只需要求出每个子树的节点数 \Large{t_i} ，和子树上每个节点到根节点的距离和 \Large{d_i} 。\ 用两次DFS即可。

再枚举每一个节点作根,对每个根枚举 v,u,i 所在子树就可以A了…………子任务1，2，4(40分)?!

才交一次就开始红温？

重新观察可以发现我们对情况1用的是这个公式(N_x为子树数):

\Huge{A_x} = \LARGE\sum_{i = 1}^{N_x}{t_i} \times (\sum_{j=i+1}^{N_x}t_j\times (\Large\sum_{k\ne i,k\ne j}^{N_x}d_k))

如果所有点都在一个根上时间复杂度就是 \Large{O} \normalsize{(n^3)}\ 所以我们只需要稍微化简一下变成这样:

\Huge{A_x} = \LARGE\sum_{i = 1}^{N_x}{t_i} \times (\sum_{j=i+1}^{N_x}t_j\times(\Large\sum_{k=1}^{N_x}d_k-d_i-d_j))

预处理出 \large\sum_{k=1}^{N}d_k 就可以轻松拿下……………64分？？！

即将结束濒临崩溃？

我们发现，即使经过化简，以上式子还是 \Large{O} \normalsize{(n^2)}\ 还是会被最后一组卡掉。\ 再次拆分式子可以拆为:

\Huge{A_x} =\LARGE\sum_{i = 1}^{N_x}{t_i} \times (\sum_{j=i+1}^{N_x}t_j\times (\Large\sum_{k=1}^{N_x}d_k-d_i)) -\LARGE\sum_{i = 1}^{N_x}{t_i} \times (\sum_{j=i+1}^{N_x}t_j\times d_j)

预处理出每一个 \large t_j\times d_j \ 再预处理出 \large \sum_{j=1}^{N}t_j 并在 \large i 每一次加一时更新。\ 就能 \Large{O} \normalsize{(n)} 求出情况1了。

然而,我们情况2时用的:

\Huge{B_x} = \LARGE\sum_{i = 1}^{N_x}{((t_i+1)} \times \sum_{j\ne i}^{N_x}d_j)

还是 \Large{O} \normalsize{(n^2)}\ 但是这个就相对很好化简了(N为节点数):

\Huge{B_x} = \LARGE\sum_{i = 1}^{N_x}{(d_i} \times (N-t_i))

现在就可以WA(如果你乱用取模的话）

现在就可以AC了

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
#include <map>
#include <vector>
#include <list>
#include <functional>
#include <stack>
#include <unordered_map>
#include <set>
#include <cctype>
#include <cstring>
#include <bitset>
#include <unordered_set>
#define m(a,b) make_pair(a,b)
#define F first
#define S second
#define us unsigned short
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
#define XOR(a,b) ((a&&!b)||(!a&&b))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M=1e9,N=2e5+5;const ll LM=1e18,P=1331,MOD=1e9+7;int YI=1,LING=0;//漫长的头文件，不用看。
ll ans;
int n;
struct zs//子树
{
    int g,t;
    ll d;
    pair<int,int> fan;
    inline void add(pair<int,ll> x)
    {
        d=x.S,t=x.F;
    }
    inline zs(int cg):g(cg){}
};
struct node
{
    bool b;//访问标记(dfs用)
    ll d;//子树d值的和
    ll dt;//子树d值*t值的和
    vector <zs> l;
} a[N];

inline pair<int,ll> dfs0(int x,ll d,int t)
{
    node &g=a[x];
    g.b=1;
    int ts=0;
    ll ds=0;
    for(auto &i:g.l)
    {
        if(!a[i.g].b)
        {
            i.add(dfs0(i.g,d+t+1,t+1));
            ds+=i.d;
            ts+=i.t;
        }
    }
    g.b=0;
    return m(ts+1,ds+ts+1);
}
inline void dfs1(int x,ll d,int t)
{
    node &g=a[x];
    g.b=1;
    g.dt=d*t;
    int ts=0;
    ll ds=0;
    for(auto &i:g.l)
    {
        if(!a[i.g].b)
        {
            ds=(ds+i.d);
            ts=(ts+i.t);
            g.dt=g.dt+i.d*i.t;
        }
        else
        {
            i.add(m(t,d));
        }
    }
    for(auto &i:g.l)
    {
        if(!a[i.g].b)
            dfs1(i.g,d+ds+ts+t-i.d-i.t+1,t+ts-i.t+1);
    }
    g.d=(ds+d);
    g.b=0;
}//前两次预处理
inline void dfs2(int x)
{
    node &g=a[x];
    g.b=1;
    int n=g.l.size();
    ll cdts=g.dt,cts=(::n-1);
    for(int i=0;i<n;i++)
    {
        zs &cs=g.l[i];
        ans=(ans+g.l[i].d*(::n-cs.t-1))%MOD;
        cts=(cts-cs.t),cdts=(cdts-cs.t*cs.d);
        ans=(ans+cs.t*(cts*(g.d-cs.d)-cdts))%MOD;
    }
    for(int i=0;i<n;i++)
    {
        if(!a[g.l[i].g].b)
            dfs2(g.l[i].g);
    }
    g.b=0;
}//最后一次计算ans
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int u,v;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        a[u].l.push_back(zs(v));
        a[v].l.push_back(zs(u));
        a[u].l.back().fan=m(v,a[v].l.size()-1);
        a[v].l.back().fan=m(u,a[u].l.size()-1);
    }
    dfs0(1,0,0);
    dfs1(1,0,0);
    dfs2(1);
    cout<<ans;
    return 0;
}