题目链接：点击打开链接
题意：
给定n个点的树[0,n)
开始所有边都是无色。
有3种操作：
1、选一个点染其相连的边 花费100
2、选一个点染其相连的2条边 花费175
3、选一个点染其相连的所有边 花费500
问：
染完所有边的最小花费。边可以重复染，点只能被操作一次。
#include #include #include #include #include #include #include #include #include #include template inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; typedef long long ll; const int N = 10100; const ll inf = 1e10; struct Edge{ int to, nex; }edge[N<<1]; int head[N], edgenum; void add(int u, int v){ Edge E = {v, head[u]}; edge[edgenum] = E; head[u] = edgenum++; } void init(){memset(head, -1, sizeof head); edgenum = 0;} int n; ll dp[N][2]; /* dp[i][0] : i的父边选了 dp[i][1] : i的父边不选 */ void up(ll &x, const ll &y){ if(y