HDU 3078 Network

Problem Description

The ALPC company is now working on his own network system, which is connecting all N ALPC department. To economize on spending, the backbone network has only one router for each department, and N-1 optical fiber in total to connect all routers. The usual way to measure connecting speed is lag, or network latency, referring the time taken for a sent packet of data to be received at the other end. Now the network is on trial, and new photonic crystal fibers designed by ALPC42 is trying out, the lag on fibers can be ignored. That means, lag happened when message transport through the router. ALPC42 is trying to change routers to make the network faster, now he want to know that, which router, in any exactly time, between any pair of nodes, the K-th high latency is. He needs your help.

Input

There are only one test case in input file. Your program is able to get the information of N routers and N-1 fiber connections from input, and Q questions for two condition: 1. For some reason, the latency of one router changed. 2. Querying the K-th longest lag router between two routers. For each data case, two integers N and Q for first line. 0<=N<=80000, 0<=Q<=30000. Then n integers in second line refer to the latency of each router in the very beginning. Then N-1 lines followed, contains two integers x and y for each, telling there is a fiber connect router x and router y. Then q lines followed to describe questions, three numbers k, a, b for each line. If k=0, Telling the latency of router a, Ta changed to b; if k>0, asking the latency of the k-th longest lag router between a and b (include router a and b). 0<=b<100000000. A blank line follows after each case.

Output

For each question k>0, print a line to answer the latency time. Once there are less than k routers in the way, print "invalid request!" instead.

Sample Input

5 5 5 1 2 3 4 3 1 2 1 4 3 5 3 2 4 5 0 1 2 2 2 3 2 1 4 3 3 5

Sample Output

3 2 2 invalid request!

Source

2009 Multi-University Training Contest 17 - Host by NUDT

Recommend

lcy   |   We have carefully selected several similar problems for you:  3071 3070 3072 3073 3074

题目大意:

给出一棵有n个节点的无根树

给出每个节点的权值

有m次询问

每次三个数x,y,z

若x==0 将y位置的数修改为z

若x!=0 询问y节点到z节点的权值总和

这道题数据规模比较小&&HDOJ的评测机速度还算快,求出LCA打暴力其实可以水过

当然如果你不介意的话可以用树链剖分+线段树+平衡树&&二分

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int MAXN=2*1e5+10;
  6 inline int read()
  7 {
  8     char c=getchar();int x=0,f=1;
  9     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
 10     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
 11 }
 12 int n,m,S=1; 
 13 int f[MAXN][21],deep[MAXN],g[MAXN];
 14 struct node
 15 {
 16     int u,v,w,nxt;
 17 }edge[MAXN];
 18 int head[MAXN];
 19 int num=1;
 20 int a[MAXN];
 21 inline void add_edge(int x,int y,int z)
 22 {
 23     edge[num].u=x;
 24     edge[num].v=y;
 25     edge[num].w=z;
 26     edge[num].nxt=head[x];
 27     head[x]=num++;
 28 }
 29 void dfs(int now)
 30 {
 31     for(int i=head[now];i!=-1;i=edge[i].nxt)
 32         if(deep[edge[i].v]==0)
 33         {
 34             deep[edge[i].v]=deep[now]+1;
 35             f[edge[i].v][0]=now;
 36             g[edge[i].v]=g[now]+edge[i].w;
 37             dfs(edge[i].v);
 38         }
 39             
 40 }
 41 inline void pre()
 42 {
 43     for(int i=1;i<=19;i++)
 44         for(int j=1;j<=n;j++)
 45             f[j][i]=f[f[j][i-1]][i-1];
 46 }
 47 inline int LCA(int x,int y)
 48 {
 49     if(deep[x]<deep[y])    swap(x,y);
 50     for(int i=19;i>=0;i--)
 51         if(deep[f[x][i]]>=deep[y])
 52             x=f[x][i];
 53     if(x==y)    return x;
 54 
 55     for(int i=19;i>=0;i--)
 56         if(f[x][i]!=f[y][i])
 57             x=f[x][i],y=f[y][i];
 58     return f[x][0];
 59 }
 60 int tot=0;
 61 int ans[MAXN];
 62 int comp(const int &a,const int &b)
 63 {
 64     return a>b;
 65 }
 66 int work(int k,int x,int y)
 67 {
 68     tot=0;
 69     int lca=LCA(x,y);
 70     while(x!=lca)    ans[++tot]=a[x],x=f[x][0];ans[++tot]=a[x];
 71     while(y!=lca)    ans[++tot]=a[y],y=f[y][0];
 72     sort(ans+1,ans+tot+1,comp);
 73     if(k>tot)    printf("invalid request!\n");
 74     else         printf("%d\n",ans[k]);
 75 }
 76 int main()
 77 {
 78     int T=1;
 79     while(T--)
 80     {
 81         n=read();m=read();
 82         for(int i=1;i<=n;i++)    a[i]=read();
 83         memset(head,-1,sizeof(head));num=1;
 84         memset(f,0,sizeof(f));
 85         memset(deep,0,sizeof(deep));
 86         for(int i=1;i<=n-1;i++)
 87         {
 88             int x=read(),y=read();
 89             add_edge(x,y,0);
 90             add_edge(y,x,0);
 91         }
 92         deep[S]=1;
 93         dfs(S);pre();
 94         while(m--)
 95         {
 96             
 97             int x=read(),y=read(),z=read();
 98             if(x==0)    a[y]=z;
 99             else work(x,y,z);
100         }    
101     }
102     
103     return 0;
104 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

4063: [Cerc2012]Darts

4063: [Cerc2012]Darts Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 85  Solve...

360110
来自专栏数据结构与算法

2018.7.30考试

题意:给出两棵树,问在两棵树中任意删除一条边后$1$号节点所在集合的元素相同的方案

12750
来自专栏开发与安全

平衡二叉树 AVL 的插入节点后旋转方法分析

平衡二叉树 AVL( 发明者为Adel'son-Vel'skii 和 Landis)是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1。 首先我...

26300
来自专栏数据结构与算法

BZOJ4517: [Sdoi2016]排列计数(组合数+错位排列)

Description 求有多少种长度为 n 的序列 A,满足以下条件: 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 的值为 i,则称 ...

30370
来自专栏小樱的经验随笔

HDU 2080 夹角有多大II

夹角有多大II Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

281100
来自专栏chenjx85的技术专栏

leetcode-458-Poor Pigs

18940
来自专栏HansBug's Lab

1295: [SCOI2009]最长距离

1295: [SCOI2009]最长距离 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 960  Solve...

29640
来自专栏ml

cf------(round)#1 C. Ancient Berland Circus(几何)

C. Ancient Berland Circus time limit per test 2 seconds memory limit per test ...

26230
来自专栏数据结构与算法

Day4晚笔记

数据结构 并查集:捆绑两个点的信息,判断对错 倍增:LCA, 字符串 hash,模拟, 最小表示法 给定一个环状字符串,切开,使得字符串的字典序最小 图和树 割...

27040
来自专栏数据结构与算法

2-SAT速成

本文只做总结性说明 2-SAT 2-SAT是k-SAT问题的一种,k-SAT问题在k>=3时已经被证明是NP完全问题 2-SAT问题定义比较简单 有n个布尔变量...

29360

扫码关注云+社区

领取腾讯云代金券