ZJOI2007 时态同步

传送门

听说这是一道树形DP，不过我不知道怎么DP，我只想出来了dfs的做法。

原题可以转化成一棵树，从给定的根节点到所有的叶节点，问要把这些路径的长度设成同一个值最少要更改多少次。

我们考虑之后发现，肯定是在深度比较低的边上做修改，使得最后的修改次数比较少，不过如何确定要修改多少次呢？我们可以先递归到叶节点，之后回溯的时候对于每一个节点， 我们可以统计这个节点的所有子树中路径最长的有多长，其他的子树只要加上差值就可以了。

这题当时想到了做法……不过做反了，从底层回溯的时候能更好的统计答案。注意在统计答案的时候不能访问到自己的父节点……所以要更改一下vis数组来记录情况。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<set>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')

using namespace std;
typedef long long ll;
const int M = 500005;
const int N = 10005;

ll read()
{
    ll ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
    if(ch == '-') op = -1;
    ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar();
    }
    return ans * op;
}

struct edge
{
    ll next,to,v,from,mt;
}e[M<<1];
ll n,s,ans,a,b,t,dis[M],head[M],ecnt;
bool vis[M];
void add(int x,int y,int z)
{
    e[++ecnt].to = y;
    e[ecnt].from = x;
    e[ecnt].v = z;
    e[ecnt].next = head[x];
    head[x] = ecnt;
}

int dfs(int x)
{
    vis[x] = 1;
    if(!head[x]) return 0;
    ll maxn = 0;
    for(int i = head[x];i;i = e[i].next)
    {
    if(!vis[e[i].to])
    {
        e[i].mt = e[i].v + dfs(e[i].to);
        maxn = max(maxn,e[i].mt);
    }
    }
    for(int i = head[x];i;i = e[i].next)
    {
    if(vis[e[i].to]) ans += maxn - e[i].mt;
    }
    return maxn;
}
int main()
{
    n = read(),s = read();
    rep(i,1,n-1) a = read(),b = read(),t = read(),add(a,b,t),add(b,a,t);
    dfs(s);
    printf("%lld
",ans);
    return 0;
}