提出 #42093643

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
#define gcd(x,y) (__gcd((x),(y)))
#define lcm(x,y) ((x)*(y)/gcd((x),(y)))
#define lg(x,y)  (__lg((x),(y)))
using namespace std;

namespace FastIO
{
	template<typename T=int> inline T read()
	{
	    T s=0,w=1; char c=getchar();
	    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	    while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
	    return s*w;
	}
	template<typename T> inline void read(T &s)
	{
		s=0; int w=1; char c=getchar();
		while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	    while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
	    s=s*w;
	}
	template<typename T,typename... Args> inline void read(T &x,Args &...args)
	{
		read(x),read(args...);
	}
	template<typename T> inline void write(T x,char ch)
	{
	    if(x<0) x=-x,putchar('-');
	    static char stk[25]; int top=0;
	    do {stk[top++]=x%10+'0',x/=10;} while(x);
	    while(top) putchar(stk[--top]);
	    putchar(ch);
	    return;
	}
}
using namespace FastIO;

namespace MTool
{	
    #define TA template<typename T,typename... Args>
    #define TT template<typename T>
    TT inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
    TT inline void cmax(T &a,T b) {a=a>b?a:b;}
    TT inline void cmin(T &a,T b) {a=a<b?a:b;}
    struct ModNum
	{
		struct fastmod
		{
		    using u128=__uint128_t; using u64=uint64_t; using u32=signed;
		    u32 f,l; u64 m,d;
		    fastmod(u64 D=998244353):d(D) 
		    {
		        const u128 ONE=1;
		        l=64-__builtin_clzll(d-1);
		        u128 M=((ONE<<(64+l))+(ONE<<l))/d;
		        if(M<(ONE<<64)) f=1,m=M; else f=0,m=M-(ONE<<64);
		    }
		    inline friend u64 operator / (u64 x,const fastmod &y)
		    {
		        if(y.f) return u128(x)*y.m>>64>>y.l;
		        else return (((x-(u128(x)*y.m>>64))>>1)+(u128(x)*y.m>>64))>>(y.l-1);
		    }
		    inline friend u64 operator % (u64 x,const fastmod &y)
		    {
		        return x-x/y*y.d;
		    }
		    inline friend u64 operator + (u64 x,const fastmod &y) {return x+y.d;}
		    inline friend u64 operator - (u64 x,const fastmod &y) {return x-y.d;}
		    inline friend bool operator == (u64 x,const fastmod &y) {return x==y.d;}
		    inline friend bool operator >  (u64 x,const fastmod &y) {return x>y.d;}
		    inline friend bool operator <  (u64 x,const fastmod &y) {return x<y.d;}
		    inline friend bool operator >= (u64 x,const fastmod &y) {return x>y.d||x==y.d;}
		    inline friend bool operator <= (u64 x,const fastmod &y) {return x<y.d||x==y.d;}
		};
		fastmod Mod;
		inline void ChangeMod(int MOD){Mod=MOD;}
		TT inline void Madd(T &a,T b) {a=a+b>Mod?a+b-Mod:a+b;}
		TT inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
		TT inline void Mmul(T &a,T b) {a=a*b%Mod;}
		TT inline void Mmod(T a) {a=(a%Mod+Mod)%Mod;}
		TT inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
		TT inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
		TT inline T Cmul(T a,T b) {return a*b%Mod;}
		TT inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
		TA inline void Madd(T &a,T b,Args... args) {Madd(a,Cadd(b,args...));}
		TA inline void Mdel(T &a,T b,Args... args) {Mdel(a,Cadd(b,args...));}
		TA inline void Mmul(T &a,T b,Args... args) {Mmul(a,Cmul(b,args...));}
		TA inline T Cadd(T a,T b,Args... args) {return Cadd(Cadd(a,b),args...);}
		TA inline T Cdel(T a,T b,Args... args) {return Cdel(Cdel(a,b),args...);}
		TA inline T Cmul(T a,T b,Args... args) {return Cmul(Cmul(a,b),args...);}
		TT inline T qpow(T a,T b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
		TT inline T qmul(T a,T b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
		TT inline T spow(T a,T b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
		private:TT inline void exgcd(T A,T B,T &X,T &Y) {if(!B) return X=1,Y=0,void(); exgcd(B,A%B,Y,X),Y-=X*(A/B);}
		public:TT inline T Ginv(T x) {T A=0,B=0; exgcd(x,Mod,A,B); return Cmod(A);}
		#undef TT
		#undef TA
	};
}
using namespace MTool;

inline void file()
{
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    return;
}

bool Mbe;

namespace LgxTpre
{
    static const int MAX=200010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    static const int mod=1e9+7;
    static const int bas=131;
    
	ModNum M;
	int n,x,y;
	vector<int> G[MAX];
	
	int f[MAX][8],g[8],u,v;
	inline void calc(int x,int y,int z) {M.Madd(g[x],M.Cmul(f[u][y],f[v][z]));}
	void dfs(int now,int father)
	{
		f[now][0]=f[now][4]=f[now][6]=1;
		for(auto to:G[now]) if(to!=father)
		{
			dfs(to,now),u=now,v=to;
			memset(g,0,sizeof g);
			calc(0,0,3);
			calc(1,1,3),calc(1,0,4),calc(1,0,1);
			calc(2,2,3),calc(2,0,6),calc(2,0,2);
			calc(3,3,3),calc(3,2,4),calc(3,1,6),calc(3,1,2),calc(3,2,1);
			calc(4,4,7);
			calc(5,5,7),calc(5,4,2),calc(5,4,6);
			calc(6,6,5);
			calc(7,7,5),calc(7,6,1),calc(7,6,4);
			memcpy(f[now],g,sizeof f[now]);
		}
	}
	
    inline void lmy_forever()
    {
    	M.ChangeMod(998244353);
    	read(n);
    	for(int i=1;i<n;++i) read(x,y),G[x].eb(y),G[y].eb(x);
    	dfs(1,0);
    	write(M.Cadd(f[1][3],f[1][5],f[1][7]),'\n');
    	return;
    }
}

bool Med;

signed main()
{
//  file();
    fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
    int Tbe=clock();
    LgxTpre::lmy_forever();
    int Ted=clock();
    cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
    return (0-0);
}

提出情報

ジャッジ結果