想請問這一題

[shut stratus]

https://zerojudge.twShowProblem?problemid=b967
如果加了斜線部分，就會TLE，所以我把感覺不必要的刪掉，結果就WA，請問為什麼這些不能刪掉?還要怎麼做才可以又快又好?

#include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
#include<utility>
#include<tuple>
#include<set>
#include<string>
#include<stack>
#include<bitset>
#define int long long
#define N 100002
#define F first
#define S second
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 10000007
using namespace std;

vector<int> edge[N];
//bool visited[N];
int maxdep;
int dfs(int a,int d){
    //visited[a]=1;
    pair<int,int> dep = {d,d};
    for(int c:edge[a]){
        //if(visited[c]) continue;
        int temp=dfs(c,d+1);
        if(temp > dep.F){
            dep.S=dep.F;
            dep.F=temp;
        }
        else if(temp>dep.S){
            dep.S=temp;
        }
    }
    maxdep=max(maxdep,dep.F+dep.S-2*d);
    //cout << maxdep;
    return dep.F;
}
signed main(){
    fastio
    int n;
    while(cin >> n){
        for(int i=1,u,v;i<n;i++){
            cin >> u >> v;
            edge[u].push_back(v);
            //edge[v].push_back(u);
        }
        dfs(0,0);
        cout << maxdep << '\n';
        for(int i=0;i<n;i++){
            edge[i].clear();
        }
        //fill(visited,visited+n+1,0);
        maxdep=0;
    }
        
}

想請問這一題

[sturdy flax]

https://zerojudge.tw/ShowProblem?problemid=b967

[pseudo skiff]

(可以講講你的解法嗎? 我記得這題好像只是兩次DFS? :o

[shut stratus]

我的做法是在dfs的時候return最深深度，pair存的是最深和次深，dep.F+dep.S-2*d是經過這個點的最長長度，所以最後的maxdep就是樹直徑長度。因為他是單向無環圖，而且每個點最多只有一個父親，所以我覺得可以不用visited

[pseudo skiff]

oh wait 你有要只需要一次DFS的解法嗎?
還是能過就好

[shut stratus]

能過就好，如果能知道我的問題在哪裡會更好

[pseudo skiff]

那我先去寫一次好了

[shut stratus]

https://tioj.ck.tp.edu.tw/problems/1152
我覺得這兩題感覺是一樣的?但是我這上面題能過，zj的就不行…

喔等等我懂了，因為我抓的不是根，所以不能用單向

[pseudo skiff]

NA (score:70%) \|/

我可以跟你講講我的解法 可以參考看看
我自己是覺得比較直觀(?)

||先建樹, 接著先用第一次dfs去找和0最遠的節點(我是維護一個值為最遠距離, 以及另一個值為最遠的的名稱)，然後再用另一個dfs去找與最遠點的最遠點||

[pseudo skiff]

是說 這個寫法是不是給次小生成樹阿 :v

[shut stratus]

#include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
#include<utility>
#include<tuple>
#include<set>
#include<string>
#include<stack>
#include<bitset>
#define int long long
#define N 100002
#define F first
#define S second
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 10000007
using namespace std;

vector<int> edge[N];
int maxdep,depdot;//最深深度、最深點

void dfs(int a,int d,int p){
    for(int c:edge[a]){
        if(c==p) continue;
        dfs(c,d+1,a);
    }
    if(maxdep<d){
        maxdep=d;
        depdot=a;
    }
}
signed main(){
    fastio
    int n;
    while(cin >> n){
        for(int i=1,u,v;i<n;i++){
            cin >> u >> v;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        dfs(0,0,-1);
        //cout << maxdep << " " << depdot;
        maxdep=0;
        dfs(depdot,0,-1);
        cout << maxdep << '\n';
        for(int i=0;i<n;i++){
            edge[i].clear();
        }
        depdot=0;
        maxdep=0;
    }
}

我改成兩次dfs了，但是還是TLE

[pseudo skiff]

[true rain]

看起來很合理

如果加上判 vis 會過嗎

[pseudo skiff]

加上vis就過了 :v

[true rain]

酷

[pseudo skiff]

但是vis跟p的作用不是一樣嗎?

[true rain]

可是我記得

樹是可以這樣用的啊

[pseudo skiff]

||(還是是測資寫爛||

[true rain]

理論上只會有一條 back edge
而那條就是祖先

[pseudo skiff]

你的寫法可以過
不過要開更多優化 xd

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

[true rain]

nani

所以這題只能用樹 DP 才能穩穩過嗎

[pseudo skiff]

[shut stratus]

所以用p的複雜度會更高嗎?

[pseudo skiff]

窩不知道 ;-;

但感覺在這題下會這樣
我自己覺得DFS或BFS都開vis比較保險

[shut stratus]

不好意思，我想再問一題dfs，我這題的最後一個測資RE，我是用一次dfs就處理所有問題

#include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
#include<utility>
#include<tuple>
#include<set>
#include<string>
#include<stack>
#include<bitset>
#define int long long
#define N 100002
#define F first
#define S second
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 10000007
using namespace std;

vector<int> edge[N];
int child[N],high[N];
bool visited[N];
int n,root,sum;

void dfs(int a,int d){
    int cnt=0,height=0;
    visited[a]=1;
    for(int c:edge[a]){
        //if(visited[c]) continue;
        if(!visited[c]){
            dfs(c,d+1);
        }
        height=max(height,high[c]);
        cnt+=child[c];//a之下的子孫數量計算
    }
    cnt++;//加上自己
    child[a]=cnt;
    //cout << a << endl;
    if(cnt==n){//子孫有n個，表示a為根
        root=a;
    }
    if(edge[a].size()) height++;
    //葉的高度為0，其他的為最大高度+1(自己)
    high[a]=height;
    sum+=high[a];
}
signed main(){
    fastio
    cin >> n;
    for(int i=1;i<n+1;i++){
        int m,u;
        cin >> m ;
        for(int j=0;j<m;j++){
            cin >> u;
            edge[i].push_back(u);
        }
    }
    //cout << "test" << endl;
    for(int i=1;i<n+1;i++){
        if(!visited[i]){
            visited[i]=1;
            dfs(i,0);
        }
    }
    cout << root << '\n' << sum << '\n';
    //for(int i=1;i<8;i++) cout << high[i] << endl;
}

[pseudo skiff]

連結? :v

||(有我不會通靈的圖或迷因嗎 或許以後用的到||

[shut stratus]

https://zerojudge.tw/ShowProblem?problemid=c463
我在耍笨

[brazen vine]

或許是遞迴太深🤔

[shut stratus]

dfs不就是每個點各跑一次嗎?為什麼會遞迴太深?

[brazen vine]

但若他的圖是一條的樣子

[brazen vine]

你的深度會到n

因為dfs到點a後，他會先繼續dfs點a連通的點，所以若abc一條，dfs順序會變成
進a 進b 進c(此時深度3) 離開c 離開b 離開a
我猜可能是這樣吧，因為我看這份code好像也沒甚麼其他問題🤔

[smoky abyss]

做得好複雜

找入度=0做樹根 再從樹根下去DFS一次不就好ㄌ

[brazen vine]

確實

但如果是遞迴過深的問題那這樣應該還是會遇到吧🤔

我之前的寫法是||把所有沒有子孫或者子孫全都跑過的點丟進queue裡面做bfs跟dp，然後最後被丟進去的點就會是根||

[smoky abyss]

我有過 那應該就不是遞迴過深

[true rain]

理論上 OJ 都會避免好的複雜度但遞迴過深的問題吧🤔

[brazen vine]

我沒聽說過誒，好像也查不太到相關資料，你是如何知道這件事的啊？

[true rain]

會把 stack 放寬吧

[brazen vine]

對誒我自己從根做dfs也有拿到AC