蒜头君的树——简单树形DP

题目链接： https://nanti.jisuanke.com/t/16446
题意：给定一棵带权树，求任意两边之间的最短距离和是多少。并且树的边权会发生改变，求每次改变后的距离和又是多少。
思路：
对于下图所示的树

我们以边为研究对象分析。
对于节点1和节点2之间的边 A，计算2、4、5到1或者3的距离时可以用到。用到的次数是 3 * (5-3) = 6次。即记以2为根的子树的节点的数量为 m，则边A被用到的次数是 m * (n-m)，那么它的贡献就是次数 * 边权。同理，可以扩展到每一个边，即 ans 为所有边的贡献之和。
例如，2到3之间的距离，是节点 1到2的边A 的距离 + 节点 1到3的边B的距离。这里A和B都被用了一次，那么A的所有次数和B的所有次数就是以2为根的子树的所有节点到 1或者3 所经过的A和B的次数和。
每次改变一条边的权值，就把这条边之前的贡献给减去，然后再加上新的贡献就是ans。
代码：

#include "bits/stdc++.h"
using namespace std;
#define fori(i,l,u) for(int i = l;i < u;i ++)
#define forj(j,l,u) for(int j = l;j < u;j ++)
#define mem(a,b) memset(a,b,sizeof(a))
#define F first
#define S second
#define pb push_back
#define mk make_pair
typedef long long  ll;
typedef pair<string, int> ps;
typedef pair<int ,int> pi;
typedef vector<int > vi;
typedef vector<ll > vl;
typedef vector<pi > vpi;
const int maxn = 1e6 + 5;
ll n;
ll ft[maxn];   // f[i] 代表i的 父节点的编号
ll dis[maxn];  //dis[i] 表示i到i的父节点的距离
ll sum[maxn];  //问题的核心， sum[i]代表 i为根的子树一共有多少节点
ll ans = 0;
void init(){
//    freopen("1.txt", "r", stdin);
    cin>>n;
    ft[1] = 1;
    fori(i, 1, n+1){
        sum[i] = 1;
    }
    fori(i, 1, n){
        cin>>ft[i+1]>>dis[i+1];
    }
    for (ll i = n; i > 0; i--) {
        sum[ft[i]] += sum[i];       //逆向遍历，因为i的父节点比i的下标小，所以从叶子节点开始遍历。
    }
    fori(i, 1, n+1){
        ans += (n-sum[i]) * sum[i] * dis[i];
    }
    cout<<ans<<endl;
}
int main()
{
    init();
    ll m,a,b;
    cin>>m;
    fori(i, 0, m){
        cin>>a>>b;
        ans -= (n-sum[a]) * sum[a] * dis[a];;
        dis[a] = b;
        ans += (n-sum[a]) * sum[a] * dis[a];
        cout<<ans<<endl;
    }
    return 0;
}

遇到的问题：一开始以为是构造树然后dfs，不过显然很傻。两点之间的距离可以分别考虑每条边的贡献来看。
更新：今天试了试一般的树形DP的方法做，就是不管它的父节点是不是直接给出，也不管特殊性，直接做。
代码：

#include "bits/stdc++.h"
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define fori(i,l,u) for(int i = l;i < u;i++)
#define forj(j,l,u) for(int j = l;j < u;j++)
#define pb push_back
#define mk make_pair
#define F first
#define S second
typedef long long  ll;
typedef pair<string, int > ps;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
const int maxn = 1e6 + 6;
ll n,x,y,m,a,b;
ll dp[maxn];
ll sum[maxn];
ll ft[maxn];
typedef struct {
    ll v;
    ll w;
}node;
vector<node> tree[maxn];
void init(){
    mem(dp,0);
    mem(sum,0);
    mem(ft,0);
}
void dfs(int cur,int ft){
    sum[cur] = 1;
    fori(i, 0, tree[cur].size()){
        int son = tree[cur][i].v;
        int len = tree[cur][i].w;
        if (son == ft) {
            continue;
        }
        dfs(son, cur);
        sum[cur] += sum[son];
        dp[cur] += dp[son] + sum[son]*(n-sum[son])*len;
    }
}
int main()
{
    init();
//    freopen("1.txt", "r", stdin);
    cin>>n;
    fori(i, 1, n){
        cin>>x>>y;
        ft[i+1] = x;
        node t1,t2;
        t1.v = x;
        t1.w = y;
        t2.v = i+1;
        t2.w = y;
        tree[i+1].pb(t1);
        tree[x].pb(t2);
    }
    dfs(1,1);
    cout<<dp[1]<<endl;
    cin>>m;
    fori(i, 0, m){
        cin>>a>>b;
        dp[1] -= sum[a]*(n-sum[a])*tree[a][0].w;
        tree[a][0].w = b;
        dp[1] += sum[a]*(n-sum[a])*b;
        cout<<dp[1]<<endl;
    }
    return 0;
}

遇到的问题：稻香村里说丰年，听取WA声一片。。。原因是各种变量都用的int，后来调试了半天，和AC代码一直对测试数据，忽然醒悟，dp[i]和sum[i]应该是longlong的范围。。

蒜头君的树——简单树形DP

相关推荐