Contest20140709 testA 树型DP

1. testA

输入文件: testA.in 输出文件testA.out 时限5000ms

问题描述：

一棵树N个节点,每条边有一个距W,现在定义SUM为所有dist(X,Y)的和1<=X<Y<=N , dist(X,Y)表示X到Y在树上的距离。现在给你一个机会把任意一条边删掉，再把这条边连接其他两个节点使得SUM最小。求出SUM的最小值

输入描述：

第一行N。

第二行到第N行每行三个数X,Y,W。表示X到Y有一条长度为W的边。

。

输出描述：

一行一个数表示答案。

数据范围N<=5000 , W<=10^6

样例输入1：

6
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1

样例输出1：

29

样例输入2：

3
1 2 2
1 3 4

样例输出2：

12

就因为这道题卡了我很久啊。总之就是维护一堆乱七八糟的值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 10000
#define MAXE MAXN*2
#define MAXV MAXN
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
typedef long long qword;
int n,m;
struct edge
{
        int x,y;
}el[MAXE];
struct Edge
{
        int np,val;
        int id;
        Edge *next;
}E[MAXE],*V[MAXV];
int root,tope=-1;
void addedge(int x,int y,int z,int id)
{
        E[++tope].np=y;
        E[tope].next=V[x];
        E[tope].val=z;
        E[tope].id=id;
        V[x]=&E[tope];
}
int fa[MAXN];
int dis_fa[MAXN];
int q[MAXN];
int ope=-1,clo=0;
int dp1[MAXN];//size of subtree
qword dp2[MAXN];//the total distance from each child to the root in subtree
qword dp3[MAXN];//the total distance from each node outside the subtree to root 
qword dp4[MAXN];//the total distance of each pair
void bfs(int root)
{
        ope=-1,clo=0;
        Edge *ne;
        q[0]=root;
        fa[root]=0;
        int now;
        while (ope<clo)
        {
                now=q[++ope];
                for (ne=V[now];ne;ne=ne->next)
                {
                        if (ne->np==fa[now])continue;
                        fa[ne->np]=now;
                        dis_fa[ne->np]=ne->val;
                        q[++clo]=ne->np;
                }
        }
}
qword  work1()
{
        int i,j;
        Edge *ne;
        int now;
        for (i=clo;i>=0;i--)
        {
                now=q[i];
                dp1[now]=1;
                for (ne=V[now];ne;ne=ne->next)
                {
                        if (ne->np==fa[now])continue;
                        dp1[now]+=dp1[ne->np];
                }
        }
        for (i=clo;i>=0;i--)
        {
                now=q[i];
                dp2[now]=0;
                for (ne=V[now];ne;ne=ne->next)
                {
                        if (ne->np==fa[now])continue;
                        dp2[now]+=dp2[ne->np]+dp1[ne->np]*ne->val;
                }
        }
        dp3[q[0]]=0;
        for (i=1;i<=clo;i++)
        {
                now=q[i];
//                dp3[now]=dp3[fa[now]]+dp2[fa[now]]-dp2[now]+dis_fa[now]*(-dp1[now]+dp1[fa[now]]-dp1[now]);
                dp3[now]=dp3[fa[now]]+dp2[fa[now]]-dp2[now]-dis_fa[now]*dp1[now]+dis_fa[now]*(dp1[root]-dp1[now]);
        }
        qword ret=0;
        for (i=1;i<=n;i++)
        {
                ret+=(qword)dis_fa[i]*dp1[i]*(dp1[root]-dp1[i]);
        }
        return ret;
}
bool edge_st[MAXN];
int color[MAXN];
qword dist[MAXN];
void dfs2(int now,int fat,int col,qword d)
{
        color[now]=col;
        dist[now]=d;
        Edge *ne;
        for (ne=V[now];ne;ne=ne->next)
        {
                if (ne->np==fat)continue;
                dfs2(ne->np,now,col,d+ne->val);
        }
}
int main()
{
        freopen("testA.in","r",stdin);
        //freopen("testA.out","w",stdout);
        int i,j,k;
        int x,y,z;
        scanf("%d",&n);
        for (i=1;i<n;i++)
        {
                scanf("%d%d%d",&x,&y,&z);
                addedge(x,y,z,i-1);
                addedge(y,x,z,i-1);
                el[i-1].x=x;
                el[i-1].y=y;
        }
        m=n-1;
        root=1;
        bfs(root);
        qword sum_old=work1();
        //cout<<"SUM_OLD:"<<sum_old<<endl;
        qword dis1,dis2;
        qword dis_old1,dis_old2;
        qword mus1,mus2;
        int totm1,totm2;
        qword best=0;
        for (i=0;i<m;i++)
        {
                edge_st[i]=1;
                if (fa[el[i].x]==el[i].y)swap(el[i].x,el[i].y);
                dfs2(el[i].x,el[i].y,1,0);//1:outside
                dfs2(el[i].y,el[i].x,2,0);//2:inside
                dis_old1=dp3[el[i].y]-dis_fa[el[i].y]*(dp1[root]-dp1[el[i].y]);
                dis_old2=dp2[el[i].y];
                mus1=dp2[el[i].y]+dp1[el[i].y]*dis_fa[el[i].y];
                mus2=dp3[el[i].y];
                totm1=dp1[el[i].y];
                totm2=dp1[root]-dp1[el[i].y];
                dis1=dis2=INF;
                for (j=1;j<=n;j++)
                {
                        if (color[j]==2)
                        {
                                dis2=min(dis2,dp2[j]+dp3[j]-mus2-totm2*dist[j]);
                        }else
                        {
                                dis1=min(dis1,dp2[j]+dp3[j]-mus1-totm1*dist[j]);
                        }
                }
                best=max(best,(dis_old1-dis1)*totm1+(dis_old2-dis2)*totm2);
        }
        printf(LL "
",sum_old-best);
        return 0;
}