HDU 4303 Hourai Jeweled 树dp 所有权利和航点 dfs2次要-白红宇

HDU 4303 Hourai Jeweled 树dp 所有权利和航点 dfs2次要

阅读量：6225 次

发布时间：2019-06-21

本文共 3016 字，大约阅读时间需要 10 分钟。

意甲冠军：

long long ans = 0;

for(int i = 1; i <= n; i++)

for(int j = i+1; j <= n; j++)

ans += F(i,j);

F(i,j)表示i点到j点路径上全部的点权和。

若i->j路径上存在2条相邻边边权同样则 F(i,j) = 0

问：ans的值。

int乘法爆掉了我也醉了。

。。

思路：

和网上的统计边方法不同，这里是用统计点出现的次数来计算

我们计算每一个点i 出现的次数，则答案就是 i的次数*i的点权 => dp[i] * a[i]

而i出现的路径起点和终点有4种

1、i的子孙->i的子孙

2、i的子孙->i

3、i到（非i的子孙（即i的祖先节点，兄弟节点和兄弟节点的子孙

4、i的子孙->非i的子孙

所以先计算1,2的情况，用dp1[i]记录

3，4的情况用dp2[i]记录

则答案就是 for(int i = 1; i <= n; i++) ans += a[i] * (dp1[i]+dp2[i]);

siz[u] 表示以u为根的子树中有效的节点数，若 u -> v(col = 1) && v -> k(col=1), 则以k为根的子树都不是有效节点

(当中v是u的儿子，k是v的儿子）

mp[u][col]表示以u为根。有效节点中用颜色为col的边相连的节点个数

#include using namespace std;#define N 300100struct Edge{	int to, col, nex;}edge[N<<1];int head[N], edgenum;void init(){memset(head, -1, sizeof head); edgenum = 0;}void add(int u, int v, int col){	Edge E = {v, col, head[u]};	edge[edgenum] = E;	head[u] = edgenum++;}typedef long long ll;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>9) pt(x/10);	putchar(x%10+'0');}int n, k;ll dp1[N], dp2[N], a[N];int siz[N];map
        
          mp[N], mp2[N];//mp[u][col]表示u子树下 边颜色=col 的有效的点数void dfs1(int u, int fa){	siz[u] = 0;    dp1[u] = 0;	for(int i = head[u]; ~i; i = edge[i].nex) {		int v = edge[i].to; if(v == fa)continue;		dfs1(v, u);		mp[u][edge[i].col] += siz[v] - mp[v][edge[i].col];		siz[u] += siz[v] - mp[v][edge[i].col];	}	ll dou = 0;	for(int i = head[u]; ~i; i = edge[i].nex) {		int v = edge[i].to; if(v == fa)continue;		dou += (ll)(siz[v] - mp[v][edge[i].col]) * (ll)(siz[u] - mp[u][edge[i].col]);		dp1[u] += siz[v] - mp[v][edge[i].col];	}	dp1[u] += dou >> 1;	siz[u]++;}void dfs2(int u, int ok, int col, int fa) {	dp2[u] = (ll)(siz[u] - mp[u][col]) * (ll)ok;	for(int i = head[u]; ~i; i = edge[i].nex) {		int v = edge[i].to; if(v == fa)continue;		if(u != fa && edge[i].col == col)			dfs2(v, siz[u] - mp[u][edge[i].col], edge[i].col, u);		else 			dfs2(v, ok + siz[u] - mp[u][edge[i].col], edge[i].col, u);	}}void solve(){	init();	for(int i = 1; i <= n; i++)rd(a[i]), mp[i].clear(), mp2[i].clear();	for(int i = 1, u, v, d; i < n; i++) {		rd(u);rd(v);rd(d);		add(u,v,d); add(v,u,d);	}	dfs1(1, 1);	dfs2(1, 0, -1, 1);}int main() {	while(rd(n)){		solve();				ll ans = 0;		for(int i = 1; i <= n; i++) 			ans += a[i]*(dp1[i]+dp2[i]);		pt( ans );putchar('\n');	}	return 0;}/*41 10 100 10001 2 12 3 13 4 151 10 100 1000 100001 2 12 3 13 4 12 5 2111 2 3 4 5 6 7 8 9 111 1231 2 11 3 22 4 32 5 13 6 33 7 35 8 15 9 28 10 111 8 2141 2 3 4 5 6 7 8 9 111 123 235 66 10001 2 11 3 22 4 32 5 13 6 33 7 35 8 15 9 28 10 111 8 212 11 28 13 18 14 2101 1 1 1 1 1 1 1 1 11 2 11 7 11 10 22 3 52 6 43 4 13 5 87 8 27 9 1141 2 5 10 20 30 70 80 100 1000 2000 5000 100000 10000001 2 21 3 11 4 12 5 22 8 33 9 33 6 24 7 14 10 33 11 36 12 213 1 214 3 3*/