2024杭电多校6-11

CODE:

  1 #include<bits/stdc++.h>
  2 #define rep(i,a,b) for(int i=a;i<=b;i++)
  3 #define dwn(i,a,b) for(int i=a;i>=b;i--)
  4 #define MAXN 102501
  5 #define inf 99999999
  6 using namespace std;
  7 typedef long long ll;
  8 inline int read(){
  9     int x=0,f=1;
 10     char ch=getchar();
 11     while(ch>'9' || ch<'0'){if(ch=='-') f=-1; ch=getchar();}
 12     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
 13     return x*f;
 14 }
 15 int n,m;
 16 int mx[MAXN],mxx[MAXN],vis[MAXN],tmp[MAXN],ans[MAXN],cird[MAXN];
 17 vector<int> v[MAXN],c;
 18 void clr(){
 19     rep(i,1,n) v[i].clear();
 20     c.clear();
 21     rep(i,1,n) mxx[i] = mx[i] = 0;
 22     rep(i,1,n) vis[i] = 0;
 23     rep(i,1,n) tmp[i] = 0;
 24     rep(i,1,n) ans[i] = 0;
 25     rep(i,1,n) cird[i] = 0;
 26 }
 27 void ade(int x, int y){
 28     v[x].emplace_back(y);
 29     v[y].emplace_back(x);
 30 }
 31 int getc(int x,int y){
 32     int res = 0,r;
 33     if(vis[x]) return x;
 34     vis[x] = 1;
 35     for(auto u : v[x]){
 36         if(u == y || tmp[u]) continue;
 37         if(!res){
 38             res = getc(u,x);
 39             if(res) c.emplace_back(x),tmp[x] = 1;
 40             if(res == x) res = 0;
 41         }
 42         else r = getc(u,x);
 43     }
 44     return res;
 45 }
 46 void dfs(int x,int y){
 47     for(auto u : v[x]){
 48         if(tmp[u] || y == u) continue;
 49         dfs(u,x);
 50         if(mx[x] < mx[u] + 1) mxx[x] = mx[x], mx[x] = mx[u] + 1;
 51         else if(mxx[x] < mx[u] + 1) mxx[x] = mx[u] + 1;
 52     }
 53     ans[x] = mxx[x] + mx[x];
 54 }
 55 void df5(int x,int y,int z){
 56     ans[x] = max(ans[x], mx[x] + z);
 57     for(auto u : v[x]){
 58         if(u == y || tmp[u]) continue;
 59         if(mx[u] + 1 == mx[x]) df5(u,x,max(z,mxx[x]) + 1);
 60         else df5(u,x,max(z,mx[x]) + 1);
 61     }
 62 }
 63 void wk1(){
 64     int u,maxx = -inf;
 65     rep(i,0,m-1){
 66         u = c[i];
 67         cird[u] = max(cird[u], maxx + i);
 68         maxx = max(maxx, mx[u] - i);
 69     }
 70     maxx = -inf;
 71     dwn(i,m-1,0){
 72         u = c[i];
 73         cird[u] = max(cird[u], maxx - i);
 74         maxx = max(maxx, mx[u] + i);
 75     }
 76     maxx = -inf;
 77     rep(i,0,m-1){
 78         u = c[i];
 79         cird[u] = max(cird[u], maxx + m - i);
 80         maxx = max(maxx, mx[u] + i);
 81     }
 82     maxx = -inf;
 83     dwn(i,m-1,0){
 84         u = c[i];
 85         cird[u] = max(cird[u], maxx + m + i);
 86         maxx = max(maxx, mx[u] - i);
 87     }
 88 }
 89 int suf[MAXN],pre[MAXN];
 90 void wk2(){
 91     suf[m] = -inf;
 92     suf[m-1] = mx[c[m-1]] + (m-1);
 93     pre[0] = mx[c[0]];
 94     int u;
 95     rep(i,1,m-1) pre[i] = max(pre[i-1], mx[c[i]] - i);
 96     dwn(i,m-2,0) suf[i] = max(suf[i+1], mx[c[i]] + i);
 97     rep(i,1,m-2) ans[c[i]] = max(ans[c[i]], pre[i-1] + suf[i+1]);
 98 }
 99 void wk3(){
100     suf[m] = -inf;
101     suf[m-1] = mx[c[m-1]] - (m-1);
102     pre[0] = mx[c[0]];
103     int u;
104     rep(i,1,m-1) pre[i] = max(pre[i-1], mx[c[i]] + i);
105     dwn(i,m-2,0) suf[i] = max(suf[i+1], mx[c[i]] - i);
106     int maxx = -inf;
107     rep(i,1,m-1){
108         ans[c[i]] = max(ans[c[i]], maxx);
109         maxx = max(maxx, pre[i-1] + mx[c[i]] - i + m);
110     }
111     maxx = -inf;
112     dwn(i,m-2,0){
113         ans[c[i]] = max(ans[c[i]], maxx);
114         maxx = max(maxx, suf[i+1] + mx[c[i]] + i + m);
115     }
116 }
117 void wk(){
118     n = read();
119     rep(i,1,n){
120         int x = read(), y = read();
121         ade(x,y);
122     }
123     int ep = getc(1,0);
124     m = c.size();
125     for(auto u : c) dfs(u,0);
126     wk1();
127     for(auto u : c) df5(u,0,cird[u]); //处理完非环点
128     wk2(); // 处理环点
129     wk3() ;
130     rep(i,1,n) printf("%d ",ans[i]);
131     puts("");
132 }
133 int main(){
134     int T = read();
135     while(T--){
136         clr();
137         wk();
138     }
139     return 0;
140 }