题意:

给出一张图(点数为n,边数为m)的一个生成树和一些非树边。

每条非树边有一个代价w，表示炸毁这条边需要付出的代价。

求炸毁一些非树边使得图中不存在偶环所付出的最小代价。

特别地，生成树上点的度数不超过10.

数据范围:n<=1000,m<=4000

分析:

首先如果一条非树边跨越了树上奇数条边，则这条边必须炸毁。

剩下的边，如果任意两条边所跨越的树上路径有公共边，则会存在偶环。

考虑到每个节点的儿子最多只有10个，我们可以考虑状压dp.

令f[x][s]表示以x为根的子树,只考虑集合s中儿子时能保留的边的最大权值。

令g[x][i]表示以x为根的子树,不考虑x的第i个儿子时能保留的边的最大权值。

每条非树边，只在它的端点的lca处考虑影响。

为了让路径不重复，则该非树边所覆盖的路径都不能被选。

暴力从一个端点到lca统计不考虑路径上的边时的最大权值。

再与该非树边没有覆盖的部分一起更新答案。

复杂度O(n*2¹⁰+n*m)

#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

#define Max(x,y) if(x<y)x=y
#define Min(x,y) if(x>y)x=y 
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=1005;
const int MAXS=1<<10;

int n,m;

struct edge{
	int t,n;
	edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
	e[++tot]=edge(t,head[s]),head[s]=tot;
	e[++tot]=edge(s,head[t]),head[t]=tot;
}

int p[MAXN],dep[MAXN];

vector<int>ch[MAXN],qy[MAXN];

void dfs(int x){
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x]){
			p[y]=x;
			dep[y]=dep[x]+1;
			ch[x].pb(y);
			dfs(y);
		}
}

inline int lca(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	while(dep[y]>dep[x])y=p[y];
	while(p[x]!=p[y])x=p[x],y=p[y];
	return x==y?x:p[x];
}

struct edge1{
	int u,v,w;
	inline void scan(){
		Scan(u),Scan(v),Scan(w);
	}
}tmp[MAXN*5];

int ans;

inline void Init(){
	Scan(n),Scan(m);
	rep(i,1,m+1){
		tmp[i].scan();
		ans+=tmp[i].w;
		if(!tmp[i].w){
			AddEdge(tmp[i].u,tmp[i].v);
		}
	}
	dfs(1);
	rep(i,1,m+1){
		if(!tmp[i].w)continue;
		int u=tmp[i].u,v=tmp[i].v;
		int Lca=lca(u,v);
		if((dep[u]+dep[v]-dep[Lca]*2)&1)continue;
		qy[Lca].pb(i);
	}
}

int dp[MAXN];

int f[MAXN][MAXS],g[MAXN][10];

inline int swim(int x,int par,int&res){
	int ban=-1;
	while(x!=par){
		if(~ban)res+=g[x][ban];
		else res+=dp[x];
		int s=ch[p[x]].size();
		rep(i,0,s)
			if(x==ch[p[x]][i]){
				ban=i; break;
			} 
		x=p[x];
	}
	return ban;
}

void tree_dp(int x){
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x])tree_dp(y);
	int s=ch[x].size();
	int maxs=1<<s;
	rep(set,0,maxs){
		int res=0;
		rep(i,0,s)
			if(set>>i&1){
				res+=dp[ch[x][i]];
			}
		Max(f[x][set],res);
	}
	int c=qy[x].size();
	rep(i,0,c){
		int u=tmp[qy[x][i]].u;
		int v=tmp[qy[x][i]].v;
		int res=tmp[qy[x][i]].w;
		int bu=max(0,1<<swim(u,x,res));
		int bv=max(0,1<<swim(v,x,res));
		rep(set,0,maxs){
			if(bu&&(set&bu)==bu||bv&&(set&bv)==bv)
				continue;
			int ns=set^bu^bv;
			Max(f[x][ns],res+f[x][set]);
		}
	}
	rep(set,0,maxs){
		rep(i,0,s)
			if(!(set>>i&1)){
				Max(g[x][i],f[x][set]);
			}
		Max(dp[x],f[x][set]);
	}
}

inline void Solve(){
	tree_dp(1);
	ans-=dp[1];
	printf("%d\n",ans);
}

int main(){
	freopen("run.in","r",stdin);
	freopen("run.out","w",stdout);
	Init(); Solve(); return 0;
} 

题意:给出一棵树，边权均视为1，对于树上每一个点u，求∑_v dis(u,v)^k

我特意去买了本混凝土数学。。。

《具体数学》:xⁿ=∑_k S₂(n,k)*A(x,k) (S₂表示第二类斯特林数，我不会用Latex别D我。。。)

这个公式的正确性显然，把有x个元素的集合划分为k个集合，允许空集的方案数为xⁿ

再做个简单的变换可以得到:xⁿ=∑_k S₂(n,k)*k!*C(x,k)

则(x+1)ⁿ=∑_k S₂(n,k)*k!*C(x+1,k)

组合数有性质:C(n,k)=C(n-1,k)+C(n-1,k-1)

则(x+1)ⁿ=∑_k S₂(n,k)*k!*(C(x,k)+C(x,k-1))=xⁿ+∑_k S₂(n,k)*k!*C(n,k-1)

实际上，我们容易发现 S₂(n,k)*k! 这个算子一直没有发生改变，所以我们可以预处理出S₂(n,k)*k!的值

令dp[x][k]=∑_{y(y属于以x为根的子树)} C(dis(x,y),k)

则dp[x][k]=∑_{y(y是与x的儿子)} dp[y][k]+dp[y][k-1]

先dfs 一次求出以1为根的所有dp值，再dfs一次，使根为当前节点x并计算 ∑_k S₂(n,k)*k!*dp[x][k]

复杂度:预处理 O(k²)+dp O(nk)

Portal

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=50005;
const int MAXK=505;
const int Mod=10007;

struct edge{
	int t,n;
	edge(int t=0,int n=0):
		t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
	e[++tot]=edge(t,head[s]),head[s]=tot;
	e[++tot]=edge(s,head[t]),head[t]=tot;
}

int n,k;

inline void Init(){
	Scan(n),Scan(k);
	rep(i,1,n+1)head[i]=0;
	tot=0;
	rep(i,1,n){
		int u,v;
		Scan(u),Scan(v);
		AddEdge(u,v); 
	}
}

int T;

int s[MAXK][MAXK],fac[MAXK];

inline void init(){
	s[0][0]=fac[0]=1;
	rep(i,1,MAXK){
		fac[i]=fac[i-1]*i%Mod;
		rep(j,1,MAXK){
			s[i][j]=(j*s[i-1][j]+s[i-1][j-1])%Mod;
		}
	}
	rep(i,1,MAXK)
		rep(j,1,MAXK){
			s[i][j]=s[i][j]*fac[j]%Mod;
		}
}

int dp[MAXN][MAXK];

void prev_dfs(int x,int p){
	dp[x][0]=1;
	rep(i,1,k+1)dp[x][i]=0;
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p){
			prev_dfs(y,x);
			rep(j,0,k+1){
				dp[x][j]+=dp[y][j];
				if(j)dp[x][j]+=dp[y][j-1];
				dp[x][j]%=Mod;
			}
		}
}

int ans[MAXN];

void dfs(int x,int p){
	ans[x]=0;
	rep(i,0,k+1)
		ans[x]=(ans[x]+s[k][i]*dp[x][i])%Mod;
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p){
			rep(j,0,k+1){
				dp[x][j]+=Mod-dp[y][j];
				if(j)dp[x][j]+=Mod-dp[y][j-1];
				dp[x][j]%=Mod;
			}
			rep(j,0,k+1){
				dp[y][j]+=dp[x][j];
				if(j)dp[y][j]+=dp[x][j-1];
				dp[y][j]%=Mod;
			}
			dfs(y,x);
			rep(j,0,k+1){
				dp[y][j]+=Mod-dp[x][j];
				if(j)dp[y][j]+=Mod-dp[x][j-1];
				dp[y][j]%=Mod;
			}
			rep(j,0,k+1){
				dp[x][j]+=dp[y][j];
				if(j)dp[x][j]+=dp[y][j-1];
				dp[x][j]%=Mod;
			}
		}
}

inline void Solve(){
	prev_dfs(1,0);
	dfs(1,0);
	rep(i,1,n+1)
		printf("%d\n",ans[i]);
}

int main(){
	for(init(),Scan(T);T--;Init(),Solve());
	return 0;
}