bzoj 3257ツリーの難題

http://www.elijahqi.win/2018/01/14/bzoj3257-%e6%a0%91%e7%9a%84%e9%9a%be%e9%a2%98/ Description
ルートのない木を与えます.ツリーにはN個のポイントがあり、エッジには重みがあります.各点に色があり、黒、白、グレーの3色の1つで、3色の木と呼ばれています.かわいいAliceは、3色の木がバランスがとれていると感じていますが、木に黒いノードが含まれていないか、白いノードが1つ以上含まれている場合だけです.しかしながら、与えられた三色ツリーは、この性質を満たしていない可能性がある.だから、Aliceはいくつかの辺を削除して形成した森の中ですべての木が均衡しているようにしようとして、費やした代価は削除した辺の重みの和に等しい.費用の最小額を計算してください.入力ファイルには、複数のテストデータが含まれています.Input
最初の行は、Tグループのテストデータがあることを示す正の整数Tを含む.次はTグループのテストデータです.各試験データのセットの最初の行には、正の整数Nが含まれる.2行目は、N個の0、1、2のいずれかの整数を含み、点1から点Nまでの色を順次表す.このうち、0は黒、1は白、2はグレーである.次のN−1行は、動作ごとに3つの整数ui、vi、c iであり、1つの重み値がciに等しいエッジ(ui、vi)を表す.Output
T行を出力し、行ごとに整数を1つずつ、各テストデータの答えを順番に表す.Sample Input
1 5 0 1 1 1 0 1 2 5 1 3 3 5 2 5 2 4 16
Sample Output 10 HINT
10の代価を費やしてエッジ(1,2)とエッジ(2,5)を削除する.
100%のデータについて:1≦N≦300,000,1≦T≦5,0≦ci<=10^9
realはとてもすばらしい问题だと思います%icefoxは后でやっとorzの巨人をしましたとても强いです
标题:各点に3色の白黒グレーがある今この木をいくつかの以下の要求を満たす木に変えることを要求して白い点だけあるかあるいは1つの白い点だけある黒い点はどうでもいい質問を求めて与えられた図を上記の要求の最小の代価に変えるのは毎回縁権を切ることができる
ではdpを設定する[x][i][j]現在のノードがx番でxがルートでi個の黒いj個の白い他のサブツリーまたは他のツリーが条件を満たす最小の代価がいくらであるかを表すなら、まず1本で木の形dpの下で私の定義がxをルートとしている以上、なぜ木の形dpもokayなのか.最後に私が要求しているのは、図全体が条件を満たすことであり、誰がルートを作るかは言わないで、xノードの上下のいくつかの辺はすべて可能である.断那不就okay转移的时候我列举子树再列举我现在ノード的状态(黑点数&白点数)对黑点>1的情况我直接累积1上对白点>2的情况我直接累积2上然后再列举子树的状态(黑点数&白点数)そして私が今来ているか、私の今の黒点数&白点数が私+子樹か、子樹との辺黒点数&白点数が私自身の比較でいいと判断します.

#include
#include
#include
#define N 330000  
#define inf 1LL<<60
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0;char ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
    return x;
}
struct node{
    int y,z,next;
}data[N<<1];
int fa[N],n,a[N],h[N],num,T;long long dp[N][2][3],tmp[2][3];
inline void insert1(int x,int y,int z){
    data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num;
    data[++num].y=x;data[num].z=z;data[num].next=h[y];h[y]=num;
}
inline void dfs(int x){
    for (int i=0;i<=1;++i) for (int j=0;j<=2;++j) dp[x][i][j]=inf;dp[x][a[x]==0][a[x]==1]=0;
    for (int i=h[x];i;i=data[i].next){
        int y=data[i].y,z=data[i].z;
        if (fa[x]==y) continue;fa[y]=x;dfs(y);
        for (int j=0;j<=1;++j) for (int z=0;z<=2;++z) tmp[j][z]=inf;
        for (int i1=0;i1<=1;++i1) for (int j1=0;j1<=2;++j1)
        if (dp[x][i1][j1]for (int ii=0;ii<=1;++ii)
        for (int jj=0;jj<=2;++jj) if (dp[y][ii][jj]int sum_white=j1+jj>2?2:jj+j1;
            tmp[i1|ii][sum_white]=min(tmp[i1|ii][sum_white],dp[x][i1][j1]+dp[y][ii][jj]);
            if (!ii||jj<2) tmp[i1][j1]=min(tmp[i1][j1],dp[x][i1][j1]+dp[y][ii][jj]+z);
        }memcpy(dp[x],tmp,sizeof(tmp));
    }
}
int main(){
    freopen("bzoj3257.in","r",stdin);
    T=read();
    while(T--){
        n=read();memset(h,0,sizeof(h));num=0;
        for (int i=1;i<=n;++i) a[i]=read();
        for (int i=1;iint x=read(),y=read(),z=read();insert1(x,y,z);}
        dfs(1);long long ans=inf;
        for (int i=0;i<=1;++i) for (int j=0;j<=2;++j) if (!i||j<2) ans=min(ans,dp[1][i][j]);
        printf("%lld
",ans);
    }
    return 0;
}