cf 500 D. New Year Santa Network
2024-10-08 15:53:09
直接按边分,2个点在边的一边,1个在另一边,组合出来就是这个边对答案的贡献,权值换了就再重新算个数而已。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
inline int ra()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
LL n,m,cnt=;
double ans,tot;
struct edge{
int from,to,next;
LL v,T;
}e[];
LL size[],head[],deep[];
void insert(int x, int y, int v)
{
e[++cnt].next=head[x]; e[cnt].from=x; e[cnt].to=y; e[cnt].v=v; head[x]=cnt;
}
void dfs(int x, int fa)
{
size[x]=;
for (int i=head[x];i;i=e[i].next)
{
if (e[i].to==fa) continue;
deep[e[i].to]=deep[x]+;
dfs(e[i].to,x);
size[x]+=size[e[i].to];
}
}
int main(int argc, char const *argv[])
{
n=ra(); tot=n*(n-)*(n-)/6.0;
for (int i=; i<n; i++)
{
int x=ra(),y=ra(),v=ra();
insert(x,y,v); insert(y,x,v);
}
dfs(,);
for (int i=; i<=cnt; i+=)
{
int now=i/,x=e[i].from,y=e[i].to;
if (deep[x]>deep[y]) swap(x,y);
LL s1=n-size[y],s2=size[y];
e[i].T+=s1*s2*((LL)n-);
ans+=e[i].T*e[i].v;
}
m=ra();
for (int i=; i<=m; i++)
{
int x=ra(),y=ra();
LL now=x*;
ans-=(e[now].v-y)*e[now].T;
e[now].v=y;
printf("%.10lf\n",(double)ans/tot);
}
return ;
}
最新文章
- .Net批量插入数据到SQLServer数据库,System.Data.SqlClient.SqlBulkCopy类批量插入大数据到数据库
- springmvc原理
- OpenCascade Shape Representation in OpenSceneGraph
- hive 记事本
- butterknife异常提示:attribute value must be constant
- Openstack的web管理端相关
- php接口和抽象类
- Python数据结构与算法--List和Dictionaries
- JSON,JSONP
- c# json转Dictionary字典
- 【转】git命令
- 关于String的相关常见方法
- c语言——第0次作业
- 统计 flv视频总时长
- 【转载】【吵架】能力 说清自己的能力。表达清楚 ;别人发飙你也要撕b;换位思考,把自己当领导层
- Spring+Mybatis+SpringMVC+Atomikos多数据源共存+不同数据库事物一致性处理
- Minimum Integer CodeForces - 1101A (思维+公式)
- 在 github 新建一个文件夹
- networkManger介绍
- Codeforces 260B - Ancient Prophesy