直接按边分,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 ;
}

最新文章

  1. .Net批量插入数据到SQLServer数据库,System.Data.SqlClient.SqlBulkCopy类批量插入大数据到数据库
  2. springmvc原理
  3. OpenCascade Shape Representation in OpenSceneGraph
  4. hive 记事本
  5. butterknife异常提示:attribute value must be constant
  6. Openstack的web管理端相关
  7. php接口和抽象类
  8. Python数据结构与算法--List和Dictionaries
  9. JSON,JSONP
  10. c# json转Dictionary字典
  11. 【转】git命令
  12. 关于String的相关常见方法
  13. c语言——第0次作业
  14. 统计 flv视频总时长
  15. 【转载】【吵架】能力 说清自己的能力。表达清楚 ;别人发飙你也要撕b;换位思考,把自己当领导层
  16. Spring+Mybatis+SpringMVC+Atomikos多数据源共存+不同数据库事物一致性处理
  17. Minimum Integer CodeForces - 1101A (思维+公式)
  18. 在 github 新建一个文件夹
  19. networkManger介绍
  20. Codeforces 260B - Ancient Prophesy

热门文章

  1. 访问docker desktop创建的Hyper-v虚拟机DockerDesktopVM
  2. Linux/CentOS环境下如何安装和配置PhantomJS工作环境
  3. C语言for循环嵌套示例
  4. openstack的一台Nova主机上的虚拟机网络的配置
  5. Hadoop基准测试(二)
  6. 在CentOS中配置java jdk环境
  7. JDBC--批量处理
  8. 机器学习(ML)十一之CNN各种模型
  9. Day2-C-迷宫问题 -POJ3984
  10. JavaWeb开发:从购买服务器到简单demo运行