提出 #73713886

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define rep(X,a,b) for(ll X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (ll)(a).size()
#define mem(a) memset(a,0,sizeof(a))
#define INF 9e18
#define EPS 1e-22
#define lc id<<1 
#define rc (id<<1)+1
#define ln seg[id].lnd
#define rn seg[id].rnd
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pll,pll> pllll;
typedef long double ld;
typedef pair<ld,ld> pdd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cout << *it << " = " << a << '\n';
	err(++it, args...);
}

pdd operator-(const pdd &a,const pdd &b){
    return mp(a.F-b.F,a.S-b.S);
}

double cross(const pdd &a,const pdd &b){
    return a.F*b.S-a.S*b.F;
}

struct Fenwick {
    int n;
    vector<int> s;
    int lowbit(int x) { return x & -x; }
    Fenwick(int _n) {
        n = _n + 1;
        s.clear(), s.resize(n, 0);
    }
    void update(int i, int v) {
        for (; i < n; i += lowbit(i))
            s[i]+=v;
    }
    int query(int x) {
        int pre = 0;
        for (; x; x -= lowbit(x))
            pre+=s[x];
        return pre;
    }
    Fenwick(vector<int> a) {
        n = a.size();
        s.clear(), s.resize(n + 1, 0);
        for (int i = 1; i <= n; i++)
            update(i, a[i - 1]);
    }
};//1 based

typedef struct linkNode{
    int val;
    struct linkNode *back=nullptr,*next=nullptr;
}LinkNode;

typedef struct ball{
    ll size;
    struct ball *boss=nullptr;
}Ball;

Ball *find(Ball *_ball){
    if(_ball==nullptr)return nullptr;
    if(_ball->boss==_ball)return _ball;
    Ball *ret=find(_ball->boss);
    return ret;
}

void ballunion(Ball *u,Ball *v){
    Ball *ub=find(u),*vb=find(v);
    if(ub==vb)return;
    if(ub->size>vb->size)vb->boss=ub,ub->size+=vb->size;
    else ub->boss=vb,vb->size+=ub->size;
}

ll gcd(ll _a,ll _b){return _b?gcd(_b,_a%_b):_a;}

double dqpow(double _x, ll _y){
    double _output=1;
    while(_y){
        if(_y&1)_output*=_x;
        _x*=_x;
        _y>>=1;
    }
    return _output;
}

ll qpow(ll _x, ll _y,ll _P){
    ll _output=1;
    while(_y){
        if(_y&1)_output=(_output*_x)%_P;
        _x=(_x*_x)%_P;
        _y>>=1;
    }
    return _output;
}

ll qqpow(ll _x, ll _y){
    ll _output=1;
    while(_y){
        if(_y&1)_output*=_x;
        _x*=_x;
        _y>>=1;
    }
    return _output;
}
    
ll v2(ll _x){
    return _x&-_x;
}

struct Node{
    ll info;
};

Node seg[800005];

void pull(ll id){seg[id].info=max(seg[lc].info,seg[rc].info);}

void modify(ll pos,ll v,ll L,ll R,ll id){
    if(pos==L&&R==pos){
        seg[id].info=v;
        return;
    }
    ll M=L+R>>1;
    if(pos<=M)modify(pos, v, L, M, lc);
    else modify(pos, v, M + 1, R, rc);
    pull(id);
}

ll query(ll l,ll r,ll L,ll R,ll id){
    if(l <= L && R <= r) return seg[id].info;
    int M=L+R>>1;
    if(r <= M) return query(l, r, L, M, lc);
    else if(l > M) return query(l, r, M + 1, R, rc);
    else return max(query(l, r, L, M, lc),query(l, r, M + 1, R, rc));
}

const ll P=998244353;
ll n,m,dp[200005],dq[200005];
// ll table[200005];
vector<ll> G[200005]={};

void dfs(ll u,ll par){
    dp[u]=0;
    dq[u]=SZ(G[u])>=3;
    for(auto i:G[u])if(i!=par){
        dfs(i,u);
        dp[u]=max(dp[u],dp[i]);
        if(SZ(G[u])>=3)dp[u]=max(dp[u],dq[i]+1);
        if(SZ(G[u])>=4)dq[u]=max(dq[u],dq[i]+1);
    }
    if(SZ(G[u])>=4){
        ll mx1=0,mx2=0;
        for(auto i:G[u])if(i!=par){
            if(dq[i]>mx2)mx2=dq[i];
            if(mx2>mx1)swap(mx1,mx2);
        }
        dp[u]=max(dp[u],mx1+mx2+1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    ll T;
    cin>>T;
    while(T--){
    //table[0]=1;
    //rep(i,1,200005)table[i]=(table[i-1]<<1)%P;
        cin>>n;
        rep(i,1,n+1)G[i].clear();
        rep(i,1,n){
            ll tmp,tmq;
            cin>>tmp>>tmq;
            G[tmp].eb(tmq),G[tmq].eb(tmp);
        }
        dfs(1,1);
        ll flag=0;
        rep(i,1,n+1)if(SZ(G[i])>=2)flag=1;
        cout<<max(flag,dp[1])<<'\n';
    }
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function 'void err(std::istream_iterator<std::__cxx11::basic_string<char> >)':
./Main.cpp:28:35: warning: unused parameter 'it' [-Wunused-parameter]
   28 | void err(istream_iterator<string> it) {}
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~^~
./Main.cpp: In function 'void modify(ll, ll, ll, ll, ll)':
./Main.cpp:142:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  142 |     ll M=L+R>>1;
      |          ~^~
./Main.cpp: In function 'll query(ll, ll, ll, ll, ll)':
./Main.cpp:150:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |     int M=L+R>>1;
      |           ~^~

ジャッジ結果