// Lupus Nocawy 26 XI 2017, PA2017 // http://potyczki.mimuw.edu.pl/ // Runda 5 // Zadanie: BAN // Banany [B] #include <cstdio> #include <algorithm> #include <vector> #include <list> #include <cmath> using namespace std; #define REP(i,n) for(int i=0, _n=n; i<_n; ++i) #define FOR(i,a,b) for(int i=(a), _b=(b); i<=_b; ++i) #define IT(i,x) __typeof__(x) i=x #define MP make_pair #define PB push_back typedef long long int lli; typedef unsigned long long int llu; typedef pair<int,int> pii; const int debug=0; const int INF = 2147483647; const lli INFm = -9223372036854775807; const int max_n = 100000; // 10^5` const int max_q = 100000; // 10^5` struct edge{ int a; // this int b; // next lli c; // cost edge(int a, int b, lli c): a(a), b(b), c(c) {}; }; vector<edge> E[max_n+1]; lli z[max_n+1]; lli profit[max_n+1]; int visited[max_n+1]; void addEdge(int a, int b, lli c){ E[a].PB(edge(a,b,c)); E[b].PB(edge(b,a,c)); } void updateEdge(int a, int b, lli d){ for(auto &it : E[a]){ if(it.b == b){ it.c = d; break; } } for(auto &it : E[b]){ if(it.b == a){ it.c = d; break; } } } void DFSr(int x, lli cost){ for(auto &it : E[x]){ int b = it.b; if(not visited[b]){ profit[b] = z[b] - cost - it.c; visited[b] = 1; DFSr(b, cost + it.c); } } } int DFS(int x, int n){ FOR(i,1,n) visited[i] = 0; profit[x] = INFm; visited[x] = 1; DFSr(x, 0); // node, cost int r = 1; // result, max profit index FOR(i,2,n){ if(profit[i] > profit[r]) r = i; } return r; } int main(void){ int n,q; scanf("%d %d ", &n, &q); FOR(i,1,n){ scanf("%lli ", z+i); } FOR(i,1,n-1){ int a,b; lli c; scanf("%d %d %lli ", &a, &b, &c); addEdge(a,b,c); } int x = 1; FOR(i,1,q){ int T; scanf("%d ", &T); if(T==1){ int v; lli d; scanf("%d %lli ", &v, &d); z[v] = d; } else /*t==2*/{ int a, b; lli d; scanf("%d %d %lli ", &a, &b, &d); updateEdge(a,b,d); } x = DFS(x,n); printf("%d ", x); } printf("\n"); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | // Lupus Nocawy 26 XI 2017, PA2017 // http://potyczki.mimuw.edu.pl/ // Runda 5 // Zadanie: BAN // Banany [B] #include <cstdio> #include <algorithm> #include <vector> #include <list> #include <cmath> using namespace std; #define REP(i,n) for(int i=0, _n=n; i<_n; ++i) #define FOR(i,a,b) for(int i=(a), _b=(b); i<=_b; ++i) #define IT(i,x) __typeof__(x) i=x #define MP make_pair #define PB push_back typedef long long int lli; typedef unsigned long long int llu; typedef pair<int,int> pii; const int debug=0; const int INF = 2147483647; const lli INFm = -9223372036854775807; const int max_n = 100000; // 10^5` const int max_q = 100000; // 10^5` struct edge{ int a; // this int b; // next lli c; // cost edge(int a, int b, lli c): a(a), b(b), c(c) {}; }; vector<edge> E[max_n+1]; lli z[max_n+1]; lli profit[max_n+1]; int visited[max_n+1]; void addEdge(int a, int b, lli c){ E[a].PB(edge(a,b,c)); E[b].PB(edge(b,a,c)); } void updateEdge(int a, int b, lli d){ for(auto &it : E[a]){ if(it.b == b){ it.c = d; break; } } for(auto &it : E[b]){ if(it.b == a){ it.c = d; break; } } } void DFSr(int x, lli cost){ for(auto &it : E[x]){ int b = it.b; if(not visited[b]){ profit[b] = z[b] - cost - it.c; visited[b] = 1; DFSr(b, cost + it.c); } } } int DFS(int x, int n){ FOR(i,1,n) visited[i] = 0; profit[x] = INFm; visited[x] = 1; DFSr(x, 0); // node, cost int r = 1; // result, max profit index FOR(i,2,n){ if(profit[i] > profit[r]) r = i; } return r; } int main(void){ int n,q; scanf("%d %d ", &n, &q); FOR(i,1,n){ scanf("%lli ", z+i); } FOR(i,1,n-1){ int a,b; lli c; scanf("%d %d %lli ", &a, &b, &c); addEdge(a,b,c); } int x = 1; FOR(i,1,q){ int T; scanf("%d ", &T); if(T==1){ int v; lli d; scanf("%d %lli ", &v, &d); z[v] = d; } else /*t==2*/{ int a, b; lli d; scanf("%d %d %lli ", &a, &b, &d); updateEdge(a,b,d); } x = DFS(x,n); printf("%d ", x); } printf("\n"); return 0; } |