#include<cstdio> #include<algorithm> #include<vector> #include<queue> #define f first #define s second #define mp make_pair using namespace std; vector <pair<int,long long> > t[100013]; pair<long long,long long> tab[100013]; int odw[100013]; int szukaj(int aktmsc, int i, vector <pair<int,long long> > [], pair<long long, long long> [], int []) { //printf ("%d %d", aktmsc, i); queue <int> q; q.push(aktmsc); tab[aktmsc].s=0; long long mx=tab[t[q.front()][0].f].f-t[q.front()][0].s; //printf ("%lld %lld ",tab[t[q.front()][0].f].f, t[q.front()][0].s); aktmsc=t[q.front()][0].f; //printf ("%lld %d ", mx, aktmsc); odw[q.front()]=i+1; while (!q.empty()) { int x=q.front(); q.pop(); for (int j=0; j<t[x].size(); j++) { if (odw[t[x][j].f]!=i+1) { odw[t[x][j].f]++; q.push(t[x][j].f); tab[t[x][j].f].s=tab[x].s+t[x][j].s; if (tab[t[x][j].f].f-tab[t[x][j].f].s>mx) { mx=tab[t[x][j].f].f-tab[t[x][j].f].s; aktmsc=t[x][j].f; } if (tab[t[x][j].f].f-tab[t[x][j].f].s==mx&&t[x][j].f<aktmsc) { mx=tab[t[x][j].f].f-tab[t[x][j].f].s; aktmsc=t[x][j].f; } } } } return aktmsc; } int main() { int n,q; long long value; int x,y; long long odl; long long new_value; int czy; long long new_odl; pair <int,long long> p; scanf ("%d %d", &n, &q); for (int i=0; i<n; i++) { scanf ("%lld", &value); tab[i+1]=mp(value,0); } for (int i=0; i<n-1; i++) { scanf ("%d %d %lld", &x, &y, &odl); p=mp(y,odl); t[x].push_back(p); p=mp(x,odl); t[y].push_back(p); } //DFS p_q int aktmsc=1; for (int i=0; i<q; i++) { scanf ("%d", &czy); if (czy==1) { scanf ("%d %lld", &x, &new_value); tab[x].f=new_value; aktmsc=szukaj(aktmsc,i,t,tab,odw); printf ("%d ", aktmsc); } else { scanf ("%d %d %lld", &x, &y, &new_odl); for (int j=0; j<t[x].size(); j++) { if (t[x][j].f==y) { t[x][j].s=new_odl; break; } } for (int j=0; j<t[y].size(); j++) { if (t[x][j].f==x) { t[y][j].s=new_odl; break; } } aktmsc=szukaj(aktmsc,i,t,tab,odw); printf ("%d ", aktmsc); } } 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 | #include<cstdio> #include<algorithm> #include<vector> #include<queue> #define f first #define s second #define mp make_pair using namespace std; vector <pair<int,long long> > t[100013]; pair<long long,long long> tab[100013]; int odw[100013]; int szukaj(int aktmsc, int i, vector <pair<int,long long> > [], pair<long long, long long> [], int []) { //printf ("%d %d", aktmsc, i); queue <int> q; q.push(aktmsc); tab[aktmsc].s=0; long long mx=tab[t[q.front()][0].f].f-t[q.front()][0].s; //printf ("%lld %lld ",tab[t[q.front()][0].f].f, t[q.front()][0].s); aktmsc=t[q.front()][0].f; //printf ("%lld %d ", mx, aktmsc); odw[q.front()]=i+1; while (!q.empty()) { int x=q.front(); q.pop(); for (int j=0; j<t[x].size(); j++) { if (odw[t[x][j].f]!=i+1) { odw[t[x][j].f]++; q.push(t[x][j].f); tab[t[x][j].f].s=tab[x].s+t[x][j].s; if (tab[t[x][j].f].f-tab[t[x][j].f].s>mx) { mx=tab[t[x][j].f].f-tab[t[x][j].f].s; aktmsc=t[x][j].f; } if (tab[t[x][j].f].f-tab[t[x][j].f].s==mx&&t[x][j].f<aktmsc) { mx=tab[t[x][j].f].f-tab[t[x][j].f].s; aktmsc=t[x][j].f; } } } } return aktmsc; } int main() { int n,q; long long value; int x,y; long long odl; long long new_value; int czy; long long new_odl; pair <int,long long> p; scanf ("%d %d", &n, &q); for (int i=0; i<n; i++) { scanf ("%lld", &value); tab[i+1]=mp(value,0); } for (int i=0; i<n-1; i++) { scanf ("%d %d %lld", &x, &y, &odl); p=mp(y,odl); t[x].push_back(p); p=mp(x,odl); t[y].push_back(p); } //DFS p_q int aktmsc=1; for (int i=0; i<q; i++) { scanf ("%d", &czy); if (czy==1) { scanf ("%d %lld", &x, &new_value); tab[x].f=new_value; aktmsc=szukaj(aktmsc,i,t,tab,odw); printf ("%d ", aktmsc); } else { scanf ("%d %d %lld", &x, &y, &new_odl); for (int j=0; j<t[x].size(); j++) { if (t[x][j].f==y) { t[x][j].s=new_odl; break; } } for (int j=0; j<t[y].size(); j++) { if (t[x][j].f==x) { t[y][j].s=new_odl; break; } } aktmsc=szukaj(aktmsc,i,t,tab,odw); printf ("%d ", aktmsc); } } return 0; } |