結果

問題 No.3346 Tree to DAG
コンテスト
ユーザー kotatsugame
提出日時 2025-11-13 21:47:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 1,672 bytes
コンパイル時間 945 ms
コンパイル使用メモリ 84,368 KB
実行使用メモリ 16,148 KB
最終ジャッジ日時 2025-11-13 21:48:07
合計ジャッジ時間 3,477 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
#include<cassert>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
int N;
vector<int>G[1<<17];
int sz[1<<17];
void dfs0(int u,int p)
{
	sz[u]=0;
	for(int v:G[u])if(v!=p)
	{
		dfs0(v,u);
		sz[u]=max(sz[u],sz[v]+1);
	}
}
vector<array<int,4> >T;
void dfs1(int u,int p,int pd)
{
	pair<int,int>mx1=make_pair(pd,p),mx2=make_pair(-1,-1),mx3=make_pair(-1,-1);
	auto upd=[&](int d,int u){
		pair<int,int>cur=make_pair(d,u);
		if(mx1<cur)mx3=mx2,mx2=mx1,mx1=cur;
		else if(mx2<cur)mx3=mx2,mx2=cur;
		else if(mx3<cur)mx3=cur;
	};
	upd(0,u);
	for(int v:G[u])if(v!=p)upd(sz[v]+1,v);
	if(mx3.first>=0)
	{
		int A=mx1.first,B=mx2.first,C=mx3.first;
		array<int,4>t;
		t[0]=A+B;
		t[1]=A+C;
		t[2]=B+C;
		sort(t.begin(),t.begin()+3);
		//reverse(t.begin(),t.begin()+3);
		t[3]=A+B+C;
		T.push_back(t);
		/*
		cout<<A<<" "<<B<<" "<<C<<endl;
		mint c=2*(mint(2).inv().pow(A+B)+mint(2).inv().pow(A+C)+mint(2).inv().pow(B+C))-3*mint(2).inv().pow(A+B+C);
		c/=4;
		c=(1-c)*mint(2).pow(N+2);
		cout<<c.val()<<endl;
		*/
	}
	for(int v:G[u])if(v!=p)
	{
		dfs1(v,u,mx1.second==v?mx2.first+1:mx1.first+1);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	for(int i=1;i<N;i++)
	{
		int u,v;cin>>u>>v;
		u--,v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs0(0,-1);
	dfs1(0,-1,-1);
	sort(T.begin(),T.end());
	//for(auto t:T)cout<<t[0]<<" "<<t[1]<<" "<<t[2]<<" "<<t[3]<<endl;
	auto t=T.back();
	mint c=2*(mint(2).inv().pow(t[0])+mint(2).inv().pow(t[1])+mint(2).inv().pow(t[2]))-3*mint(2).inv().pow(t[3]);
	c/=4;
	c=(1-c)*mint(2).pow(N+2);
	cout<<c.val()<<endl;
}
0