POJ3585 换根模板

题意：机翻？

好，假装各位都已经看懂了题。

首先是暴力，枚举每一个点作为根，然后每次做一个树上DP，复杂度O(n²)，Ｔ掉；

然后，我们考虑怎样优化。

假设我们已经求出了ｘ的答案，对与每一个它的子节点，

我们注意到其实当我们换其子节点ｙ为根时，ｙ的子树贡献是已知的。

只需考虑另外一侧的贡献之间，

同时又注意到，除ｙ以外的对ｘ的贡献就是ｘ的答案减掉ｙ对它的贡献，也是一定的。

所以只有ｘ会影响到ｙ，直接根据限制在ｙ和ｘ之间转移一下就好了。

#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
inline int gi () {
    int x=0, w=0; char ch=0;
    while (! (ch>='0' && ch<='9') ) {
        if (ch=='-') w=1;
        ch=getchar ();
    }
    while (ch>='0' && ch<='9') {
        x= (x<<3) + (x<<1) + (ch^48);
        ch=getchar ();
    }
    return w?-x:x;
}

const int N=2e5+10;
int T,n,tot,ans,head[N],f[N],Deg[N],ind[N],vis[N],leaf[N];

struct Edge {
    int next, now, val;
}e[N<<1];
inline void make (int from, int to, int va) {
    e[++tot].next=head[from];
    e[tot].now=to;
    e[tot].val=va;
    head[from]=tot;
}

void New_case () {
    tot=0; ans=0;
    memset (f, 0, sizeof (f) );
    memset (&e, 0, sizeof (e) );
    memset (ind, 0, sizeof (ind) );
    memset (vis, 0, sizeof (vis) );
    memset (Deg, 0, sizeof (Deg) );
    memset (head, 0, sizeof (head) );
}

void DP (int k) {
    vis[k]=1;
    int fl=1;
    for (int i=head[k];i;i=e[i].next) {
        int x=e[i].now;
        if (vis[x]) continue;
        DP (x);fl=0;
        if (ind[x]==1) Deg[k]+=e[i].val;
        else Deg[k]+=min (Deg[x], e[i].val);
    }
    leaf[k]=fl;
}

void DFS (int p) {
    vis[p]=1;
    for (int i=head[p];i;i=e[i].next) {
        int k=e[i].now;
        if (vis[k]) continue;
        if(leaf[k]) {
            f[k]=f[p]-e[i].val;
            continue;
        }
        if (ind[p]==1) f[k]=Deg[k]+e[i].val;
        else f[k]=Deg[k]+min (e[i].val, f[p]-min (e[i].val, Deg[k]) );
        DFS (k);
    }    
}

int main ()
{
    T=gi ();
    while (T--) {
        n=gi ();
        New_case ();
        for (int i=1, x, y, z;i<n;++i) {
            x=gi (), y=gi (), z=gi ();
            ind[x]++, ind[y]++;
            make (x, y, z);
            make (y, x, z);
        }
        DP (1);
        memset (vis, 0, sizeof (vis) );
        f[1]=Deg[1];
        DFS (1); // 换根
        for (int i=1;i<=n;++i)
            ans=max (ans, f[i]);
        printf ("%d
", ans);
    }
    return 0;
}