江苏省住房和城乡建设局网站,泉山微网站开发,网站不支持m.域名,wordpress 安装 模板正题 题目大意
一棵树#xff0c;一条边的权是原本的权值减去出发点的加速。 求一个点使得这个点到所有点路径边权和最小。 解题思路
我们先求出以1为根时的答案 然后用换根法 我们从1转移到2#xff0c;我们会发现 红色的部分的路径都减去的紫色的路径长度#xff0c;蓝…正题 题目大意
一棵树一条边的权是原本的权值减去出发点的加速。 求一个点使得这个点到所有点路径边权和最小。 解题思路
我们先求出以1为根时的答案 然后用换根法 我们从1转移到2我们会发现 红色的部分的路径都减去的紫色的路径长度蓝色的部分路径长度都加上这条紫色的路径注意因为出发点不同所以权值不同 所以我们推出根转移方程 fyfx−numy∗(w−movx)(n−numy)∗(w−movy)f_yf_x-num_y*(w-mov_x)(n-num_y)*(w-mov_y)fyfx−numy∗(w−movx)(n−numy)∗(w−movy) code
#includecstdio
#includealgorithm
#includecstring
#define ll long long
#define N 700010
using namespace std;
struct line{ll to,w,next;
}a[N*2];
ll ls[N],mov[N],x,y,w,n,f[N],num[N],tot,ans;
int read(){char cgetchar();int x0;for(;0c||c9;cgetchar());for(;0cc9;cgetchar()) xx*10(c-0);return x;
}
void addl(ll x,ll y,ll w)
{a[tot].toy;a[tot].ww;a[tot].nextls[x];ls[x]tot;
}
void dp(ll x,ll fa)//计算第一个答案和子树大小
{num[x]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(y!fa){dp(y,x);f[1]max(a[i].w-mov[x],0ll)*num[y];num[x]num[y];}}
}
void dp2(ll x,ll fa)//转移根
{if(f[x]f[ans]||(f[x]f[ans]xans)) ansx;//统计答案for(ll ils[x];i;ia[i].next){ll ya[i].to;if(y!fa){f[y]f[x]-num[y]*(a[i].w-mov[x])(n-num[y])*(a[i].w-mov[y]);//动态转移dp2(y,x);}}
}
int main()
{nread();for(ll i1;in;i)mov[i]read();for(ll i1;in;i){xread();yread();wread();addl(x,y,w);addl(y,x,w);}dp(1,0);ans1;dp2(1,0);printf(%lld\n%lld,ans,f[ans]);
}
