// 第二题 我记得很久很久很久以前看过这样的题目,忘记是哪的区域赛了

// 记得有人说和节点度数有关,我记不清了,反正当时完全不懂

// 然后我想了想,估计就是更新节点度数有关,YY出来可能只要更新相邻节点度数更大或更小的就可以了

// 复杂度不知道多少,就是提交了试试,15MS就过了

// 看来就是这样了

// 具体就是求出每个节点度数,然后每次更新时,只要更新与自己相连,但度数比自己大的

// 查询时把度数自己大的节点累加的值加上就可输出,具体看代码比较清楚

// 也就做得来这2题了(见识少,以前题目做得少)。

// 不过在厦门实训感觉蛮悠闲,企业上课就是比学校效率

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define LL long long
#define N 100010
#define mod 1000000007
vector<int> V[N],up[N];//V记录边,up记录邻接节点,但度数自己大
int in[N];//记录节点度数
int sum[N],add[N];//add 保存更新
int main()
{
// priority_queue<int,vector<int>,greater<int> >
int T;
int n,m,Q;
int a,b;
int i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&m);
for(i=;i<=n;i++){
V[i].clear();
in[i]=;
up[i].clear();
sum[i]=add[i]=;
}
while(m--)
{
scanf("%d %d",&a,&b);
V[a].push_back(b);
V[b].push_back(a);
in[b]++;
in[a]++;
} for(a=;a<=n;a++)
for(j=;j<V[a].size();j++)
{
b=V[a][j];
if(in[b]>=in[a])
up[a].push_back(b);
}
scanf("%d",&Q);
int cmd,u,v;
while(Q--)
{
scanf("%d %d",&cmd,&u);
if(cmd==)
{
scanf("%d",&v);
add[u]+=v;
for(i=; i<up[u].size(); i++)
{
j=up[u][i];
sum[j]+=v;
}
}
else
{
int ans=sum[u];
for(i=; i<up[u].size(); i++)
{
j=up[u][i];
if(in[j]!=in[u])
ans+=add[j];
}
printf("%d\n",ans);
}
} }
return ;
}

最新文章

  1. Android 开源框架Universal-Image-Loader完全解析(一)--- 基本介绍及使用
  2. MySQL substring:字符串截取 (转载)
  3. java(搜索不区分大小写)
  4. java 面向对象编程 第18章——网络编程
  5. css初始化代码方案
  6. 利用Unicode属性移除文本中的标点符号
  7. hdu 3389 Game 博弈论
  8. c语言指针数组与数组指针
  9. js-call、apply
  10. 测试web网站兼容性的方法
  11. 原生js实现简单移动端轮播图
  12. Java对象引用/JVM分级引用——强引用、软引用、弱引用、虚引用
  13. SQLServer之创建隐式事务
  14. Fragment的粗浅理解
  15. Ubuntu 18.04学习笔记
  16. WPF学习笔记(6):DataSet更新后台数据库个别列失败的问题
  17. php 请求另一个服务器接口返回数据
  18. git 认识
  19. Restrictions用法
  20. 用Lingo求解线性规划问题

热门文章

  1. RabbitMQ 的路由模式 Topic模式
  2. Excel_To_DataTable
  3. fis 前端构建工具
  4. CodeForces 297C Splitting the Uniqueness (脑补构造题)
  5. linux 普通synflood攻击防范网络参数设置
  6. AngularJS如何修改URL中的参数
  7. GPON命令模式
  8. NPOI自定义单元格背景颜色
  9. LeetCode OJ:Range Sum Query - Immutable(区域和)
  10. djagno重写authenticate实现帐号和邮箱的多方式登录。